Hot answers tagged

9

The mistake I made was in the very last step: flipping the result. Doing that requires more than an $\mathsf{NP}$ machine, because I'm recombining the massively parallel computation then doing something else. $\mathsf{NP}$ machines finish with the merging, they can't continue on. To run my algorithm I'd need a machine with the ability to query an $\mathsf{...


8

I take it that we call $TAUT$ the problem of given a DNF formula, decide if it is a tautology (if you do not want to restrict to DNF, this will still work as this only makes the problem more general). The answer of your questions easily follows from the definition of $coNP$. Remember that a language $L \subseteq \{0,1\}^*$ is in $coNP$ is $\bar{L} = \{x \in ...


6

Not very far. The approach that you are describing is known as proof complexity, and it is covered by several surveys and lecture notes. There are several kinds of proof system being considered: Frege systems. These are systems in which a proof consists of a sequence of formulas or circuits (depending on the system), and there is a fixed set of derivation ...


6

The Definitions This comes from the one-sidedness of the definition $NP$, that (we think) is inherent to the class. One definition of $NP$ is the set of languages $L$ such that there is some for every $x \in L$, there exists a certificate $c$ polynomial-sized relative to $x$, and an algorithm to check if $c$ is a valid certificate that runs in polynomial ...


5

The decision problem version of integer linear programming is known to be in NP. In particular, determining whether an integer linear program has a feasible solution is in NP. It is known that if an integer linear program has a feasible solution, then it has a feasible solution whose length (in bits) is at most a polynomial in the length (in bits) of the ...


5

The notion of duality suggested by the discrete Farkas lemma found in Lasserre's paper does not correspond to an integer program. There is a notion of duality for integer programs (see for example here), but strong duality does not hold, so I doubt it can be used along the lines you suggest.


5

If SAT is in coNP then NP=coNP, which is believed to be false. However, coSAT, the language of unsatisfiable CNFs, is coNP-complete.


4

It is not known whether NP=coNP or NP≠coNP, but the latter is strongly suspected. It is not even known whether P≠NP implies NP≠coNP. It is known that NP≠coNP implies P≠NP, and this approach for proving P≠NP is known as "Cook's program". Now to your particular proof system. As far as I understand, your proof system maintains a collection of DNFs, which are ...


4

You just need to show that swapping final and non-final states doesn't complement the language accepted by an NTM, e.g., by showing that, for at least one NTM $N$ (which you can construct to have whatever properties you need), there is a string that is accepted by both $N$ and $N'$, or rejected by both.


4

If SAT is in coNP then since coSAT is coNP-complete, SAT can be reduced to coSAT in polytime. The same reduction also reduces coSAT to SAT. Since coSAT is coNP-complete, every problem in coNP can be reduced in polytime to coSAT, and so to SAT. This shows that SAT is coNP-complete.


4

The answer is no, and the reason is that $\mathrm{P}$ is trivially closed under complement. Just by definition of $\mathrm{co}$, it follows that $\mathrm{coNP} = \mathrm{P}$ is equivalent to $\mathrm{NP} = \mathrm{coP}$, and then we use that $\mathrm{coP} = \mathrm{P}$ to conclude that $\mathrm{coNP} = \mathrm{P}$ iff $\mathrm{NP} = \mathrm{P}$.


3

If we are assuming that $coNP≠𝑁𝑃$, we can conclude that every language that is $co NP$ complete is not in $NP$ (a contradiction to your given assumption). Thus, every language we already know of that is $coNP$ complete, is complete as well in $coNP -NP$.


3

The theorem is false. There is a circuit of size $\tilde{O}(2^n)$ that solves SAT. At any rate, the relevant conjectures you would be proving using statements of this form are the Exponential time hypothesis and its variants.


3

The definition you give in the quesition is very imprecise so it's understandable that you've misunderstood it. The formal definitions are given at our reference question on NP. A decision problem is in NP if there's some polynomial $p$ and an ordinary, deterministic polynomial-time Turing machine $M$ such that: For every "yes" instance $x$,...


3

Your question assumes $NP \neq coNP$, which is currently unknown (but generally assumed to be true). If $NP = coNP$, there is no problem satisfying your requirements. If $NP \neq coNP$, the complement of any NP-complete problem works. You can find a list on Wikipedia.


3

co-NP is the set of complements of problems that are in NP. So co-NP contains problems such as non-3-colourability, Boolean unsatisfiability and so on. Most complexity theorists believe that NP$\,\neq\,$co-NP and one consequence of this is that the complement of any NP-complete problem would be in co-NP but not in NP. Wikipedia has more information on co-NP....


3

First of all, you're misstating integer factorization: your version is completely equivalent to primality. Second, there were primality certificates which could stand for a polytime primality testing algorithm. These are polytime verifiable certificates of primality.


3

It is known that co-NP $\subseteq$ PSPACE $\subseteq$ EXPTIME, so every EXPTIME-hard problem, must also be a co-NP-hard problem (as there is a polynomial time reduction from every $L\in$ EXPTIME to it, and therefore also from every $L\in$ co-NP) Therefore EXPTIME-hard $\subseteq$ co-NP-hard. Note that this argument does not hold for co-NP-complete and ...


2

Under the assumption that $NP\neq \mathrm{co}NP$, we have that: $$P^{SAT[1]}=NP\cup \mathrm{co}NP\implies P^{NP[1]}\neq P^{NP[2]}$$ Proof: Since $D^p\subseteq P^{NP[2]}$, we deduce that $(SAT\dot{\land} UNSAT)\in P^{NP[2]}$. Meanwhile, $(SAT\dot{\land}UNSAT)\notin NP$ due to $UNSAT\notin NP$ and similarly, $(SAT\dot{\land}UNSAT)\notin \mathrm{co}NP$ due ...


2

Independent set is NP-complete, so it's unlikely to be in coNP. Moreover, the complement problem would sound like "all independent sets have size at most $s$".


2

A problem in NP can be solved quickly if the answer is YES. Your inverted Turing machine finds the answer quickly if the answer to the original question is YES and the answer to the inverted question is NO. You need an answer quickly if the answer to the inverted question is YES and to the original is NO, and you don't have that. Edit: Take for example the ...


2

We don't define problems to be NP-complete. We define classes of problems, define the concept of completeness for those classes, and then prove that problems are complete, because they have the properties that define completeness. Analogously, we don't define 13 to be prime; rather, we define the property of being prime and then prove that 13 has that ...


2

No, the steps are insufficient. You need to use a Karp reduction, since that's the type of reduction used in the definition of coNP-completeness. SAT is NP-complete, but probably not coNP-complete (unless NP=coNP); and coSAT is coNP-complete, but probably not NP-complete. This distinction would be lost if you used Cook reductions. Some questions on this ...


2

The complement (note spelling) of $\mathrm{SAT}$ is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all. In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, ...


2

The proof does bot need to be a subset. It might be another indicator that the given set has a some stricture preventing it from being a positive instance of the subsetsums problem. A good example with a non-trivial certificate is linear programming. Linear programs admit both a positive and a negative certificate (For the question whether the optimal can be ...


2

Read the definition of NP and co-NP. By that definition, every problem in P is automatically both in NP and co-NP. There’s nothing to prove, that’s how they are defined.


2

I think you might be confusing a couple of things. First, the complement of any problem in NP is in CoNP by definition. No further conditions are required. Second, admitting a polynomial time algorithm to verify solutions, and belonging to the class NP, are equivalent statements. Third, Goldbach's conjecture is a mathematical statement, which under ...


1

Specifically speaking, 3-SAT is an example of NP-Complete problem. But your problem is only considered with NP problems. We have the decision problem: Is a SAT problem in NP? Obviously, it is. Because you could always verify a "certificate" in time linear to your input size (values of your literals, that is a sequences of 0s and 1s). For your question: ...


1

Given a $\overline{SAT}$ instance $\psi$ with $m$ clauses, let $\phi$ be the formula formed by adding to each clause a new variable $x$ (the same for all clauses), and a new clause $\bar{x}$. If $\psi$ is satisfiable then $\phi$ is satisfiable, whereas if $\psi$ is unsatisfiable then the maximum number of clauses that can be satisfied is $m$.


1

A co-NP problem differs from its complementary NP problem exactly by being its complement! That's the whole story. NP problems should accept YES instances -> instances where the answer is yes. I think you've confused yourself. Every problem, of any complexity, is a division of all possible instances into "yes" instances and "no" instances. For TSP, the "...


Only top voted, non community-wiki answers of a minimum length are eligible