We study the complexity of computing second solutions for NP search problems, i. e., given a problem instance x and a valid solution y, we have to find another valid solution y'. Our main result shows that for typical NP decision problems, the complexity of computing second solutions is completely determined by the choice of the type of solution (i. e., the specific function problem), but independent of the underlying decision problem. More precisely, we show that for every X ∈ NP that is 1-paddable (a weak form of paddability), different choices of the type of solution lead to different second solution problems, which altogether have the same degree structure as the entire class of NP search problems (FNP). In fact, each degree of difficulty within FNP does occur as a second solution problem for X. This proves that typical NP decision problems have no intrinsic complexity w. r. t. the search for a second solution, but only the specification of the type of solution determines this complexity. This explains the empirical observation that the difficulty of computing second solutions strongly depends on the formulation of the problem. Moreover, we show that the complexities of a search problem and its second solution variant are independent in the following sense: For all search problems A and B representing two degrees of difficulty, there exists a search problem C such that 1) C is as difficult as A and 2) computing second solutions for C is as difficult as B.

We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over $\mathrm{NP}$. Our main results concern $\mathrm{DP}$, i.e., the second level of this hierarchy: If all sets in $\mathrm{DP}$ have p-optimal proof systems, then all sets in $\mathrm{coDP}$ have p-optimal proof systems. The analogous implication for optimal proof systems fails relative to an oracle. As a consequence, we clarify such implications for all classes $\mathcal{C}$ and $\mathcal{D}$ in the Boolean hierarchy over $\mathrm{NP}$: either we can prove the implication or show that it fails relative to an oracle. Furthermore, we show that the sets $\mathrm{SAT}$ and $\mathrm{TAUT}$ have p-optimal proof systems, if and only if all sets in the Boolean hierarchy over $\mathrm{NP}$ have p-optimal proof systems which is a new characterization of a conjecture studied by Pudlák.

We construct an oracle relative to which $\mathrm{P} = \mathrm{NP} \cap \mathrm{coNP}$, but there are no many-one complete sets in $\mathrm{UP}$, no many-one complete disjoint $\mathrm{NP}$-pairs, and no many-one complete disjoint $\mathrm{coNP}$-pairs. This contributes to a research program initiated by Pudlák [Pud17], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that $\mathsf{NP}\cap\mathsf{coNP}$ is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.

The article investigates the relation between three well-known hypotheses. - H_{union}: the union of disjoint ≤^p_m-complete sets for NP is ≤^p_m-complete - H_{opps}: there exist optimal propositional proof systems - H_{cpair}: there exist ≤^{pp}_m-complete disjoint NP-pairs The following results are obtained: - The hypotheses are pairwise independent under relativizable proofs, except for the known implication H_{opps} ⇒ H_{cpair}. - An answer to Pudlák’s question for an oracle relative to which ¬H_{cpair}, ¬H_{opps}, and UP has ≤^p_m-complete sets. - The converse of Köbler, Messner, and Torán’s implication NEE ∩ TALLY ⊆ coNEE ⇒ H_{opps} fails relative to an oracle, where NEE =^{df} NTIME(2^O(2ⁿ)). - New characterizations of H_{union} and two variants in terms of coNP-completeness and p-producibility of the set of hard formulas of propositional proof systems.

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT). Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC(\cup,\cap,¯,+,×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(\cup,\cap,¯,+,×) studied by Glaßer et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a major open problem in algebraic computing complexity: 1. membership problem MC(\cap,+,×) studied by McKenzie and Wagner 2007 2. integer membership problems MC_Z(+,×), MC_Z(\cap,+,×) studied by Travers 2006 3. equivalence problem EQ(+,×) studied by Glaßer et al. 2010

We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and randomized 2/3-approximable on undirected graphs. Using the same technique we show that the multiobjective maximum satisfiablilty problem is 1/2-approximable.

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results: - The classes of the Boolean hierarchy over level $Sigma_1$ of the dot-depth hierarchy are decidable in $NL$ (previously only the decidability was known). The same remains true if predicates mod $d$ for fixed $d$ are allowed. - If modular predicates for arbitrary $d$ are allowed, then the classes of the Boolean hierarchy over level $Sigma_1$ are decidable. - For the restricted case of a two-letter alphabet, the classes of the Boolean hierarchy over level $Sigma_2$ of the Straubing-Th{'\e}rien hierarchy are decidable in $NL$. This is the first decidability result for this hierarchy. - The membership problems for all mentioned Boolean-hierarchy classes are logspace many-one hard for $NL$. - The membership problems for quasi-aperiodic languages and for $d$-quasi-aperiodic languages are logspace many-one complete for $PSPACE$.

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaßer et al., complete sets for all of the following complexity classes are m-mitotic: $\mathrm{NP}$, $\mathrm{coNP}$, $\oplus\mathrm{P}$, $\mathrm{PSPACE}$, and $\mathrm{NEXP}$, as well as all levels of $\mathrm{PH}$, $\mathrm{MODPH}$, and the Boolean hierarchy over $\mathrm{NP}$. In the cases of $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and $\mathrm{PH}$, this at once answers several well-studied open questions. These results tell us that complete sets share a redundancy that was not known before. In particular, every $\mathrm{NP}$-complete set A splits into two $\mathrm{NP}$-complete sets $A_1$ and $A_2$. We disprove the equivalence between autoreducibility and mitoticity for all polynomial-time-bounded reducibilities between 3-tt-reducibility and Turing-reducibility: There exists a sparse set in $\mathrm{EXP}$ that is polynomial-time 3-tt-autoreducible, but not weakly polynomial-time T-mitotic. In particular, polynomial-time T-autoreducibility does not imply polynomial-time weak T-mitoticity, which solves an open question by Buhrman and Torenvliet.

We study several properties of sets that are complete for NP. We prove that if L is an NP‐complete set and S \not\supseteq L is a p‐selective sparse set, then $L - S$ is $\leq^{p}_{m}$‐hard for NP. We demonstrate the existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$ such that for every $L \in \mbox{NP} - \mbox{P}$, L - S is not $\leq^p_m$‐hard for NP. Moreover, we prove for every $L \in \mbox{NP} - \mbox{P}$ that there exists a sparse $S \in $ EXP such that L - S is not $\leq^p_m$‐hard for NP. Hence, removing sparse information in P from a complete set leaves the set complete, while removing sparse information in EXP from a complete set may destroy its completeness. Previously, these properties were known only for exponential time complexity classes. We use hypotheses about pseudorandom generators and secure one‐way permutations to derive consequences for longstanding open questions about whether NP‐complete sets are immune. For example, assuming that pseudorandom generators and secure one‐way permutations exist, it follows easily that NP‐complete sets are not p‐immune. Assuming only that secure one‐way permutations exist, we prove that no NP‐complete set is DTIME$(2^{n^{\epsilon}})$‐immune. Also, using these hypotheses we show that no NP‐complete set is quasi‐polynomial‐close to P. We introduce a strong but reasonable hypothesis and infer from it that disjoint Turing‐complete sets for NP are not closed under union. Our hypothesis asserts the existence of a UP‐machine M that accepts $0^*$ such that for some $0 < \epsilon < 1$, no $2^{n^{\epsilon}}$ time‐bounded machine can correctly compute infinitely many accepting computations of M. We show that if $\UP \cap \co\UP$ contains DTIME$(2^{n^{\epsilon}})$‐bi‐immune sets, then this hypothesis is true.

We study several properties of sets that are complete for NP. We prove that if L is an NP-complete set and S /spl nsupe/ L is a p-selective sparse set, then L -S is /spl les//sub m//sup p/-hard for NP. We demonstrate existence of a sparse set S /spl isin/ DTIME(2/sup 2n/) such that for every L /spl isin/ NP - P, L - S is not /spl les//sub m//sup p/-hard for NP. Moreover, we prove for every L /spl isin/ NP - P, that there exists a sparse S /spl isin/ EXP such that L - S is not /spl les//sub m//sup p/-hard for NP. Hence, removing sparse information in P from a complete set leaves the set complete, while removing sparse information in EXP from a complete set may destroy its completeness. Previously, these properties were known only for exponential time complexity classes. We use hypotheses about pseudorandom generators and secure one-way permutations to derive consequences for long-standing open questions about whether NP-complete sets are immune. For example, assuming that pseudorandom generators and secure one-way permutations exist, it follows easily that NP-complete sets are not p-immune. Assuming only that secure one-way permutations exist, we prove that no NP-complete set is DTIME(2/sup ne/)-immune. Also, using these hypotheses we show that no NP-complete set is quasipolynomial-close to P. We introduce a strong but reasonable hypothesis and infer from it that disjoint Turing-complete sets for NP are not closed under union. Our hypothesis asserts existence of a UP-machine M that accepts 0* such that for some 0 < /spl epsi/ < 1, no 2/sup ne/ time-bounded machine can correctly compute infinitely many accepting computations of M, We show that if UP /spl cap/ coUP contains DTIME(2/sup ne/)-bi-immune sets, then this hypothesis is true.

Razborov (1994) proved that existence of an optimal proof system implies existence of a many-one complete disjoint NP-pair. Kobler, Messner, and Toran (2003) defined a stronger form of many-one reduction and claimed to improve Razborov's result by showing under the same assumption that there is a strongly many-one complete disjoint NP-pair. Here we show that the two results are equivalent. More generally, we prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A,B) and (C,D) is a Turing reduction with the additional property that if the input belongs to A /spl cup/ B, then all queries belong to C /spl cup/ D. We prove under the reasonable assumption UP /spl cap/ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A,B) and (C,D) such that (A,B) is truth-table reducible to (C,D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DisjNP has a truth-table-complete disjoint NP-pair, but has no many-one- complete disjoint NP-pair.

We study the question of whether the class DisjNP of disjoint pairs (A, B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets that is NP-hard. We show under reasonable hypotheses that nonsymmetric disjoint NP-pairs exist, which provides additional evidence for the existence of P-inseparable disjoint NP-pairs. We construct an oracle relative to which the class of disjoint NP-pairs does not have a complete pair; an oracle relative to which optimal proof systems exist, and hence complete pairs exist, but no pair is NP-hard; and an oracle relative to which complete pairs exist, but optimal proof systems do not exist.

We study the question of whether the class DisNP of disjoint pairs (A, B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets that is NP-hard. We show under reasonable hypotheses that nonsymmetric disjoint NP-pairs exist, which provide additional evidence for the existence of P-inseparable disjoint NP-pairs. We construct an oracle relative to which the class of disjoint NP-pairs does not have a complete pair, an oracle relative to which optimal proof systems exist, hence complete pairs exist, but no pair is NP-hard, and an oracle relative to which complete pairs exist, but optimal proof systems do not exist.