# Questions tagged [co-np]

Question about the complexity class that is a complement of NP, i.e. decision problems where the "no" instances can be accepted by a nondeterministic Turing machine that runs in time polynomial in the length of the input.

59 questions
Filter by
Sorted by
Tagged with
40 views

### Can these variants of SAT/Tautology be actually pretty simple?

There are 8 (very similiar) languages I'd like to discuss here: CNF SAT DNF SAT CNF No-SAT (Existence of a false assignment) DNF No-SAT CNF Tautology DNF Tautology CNF Contradiction DNF Contradiction ...
34 views

### Why don't we consider that NP = co-NP while we can reduce Tautology problem into Satisfiability in polynomail time easily?

Let's determine if an expression is tautological or not and let's try this expression: ((a ⊼ b) ∨ c) ↔ (¬a ∨ ¬b ∨ c). We can turn this problem into CIRCUIT-SAT decision problem by asking if the ...
19 views

### Where are some examples of unsatisfiable formulas? Especially about 3CNF paradigm

I've been learning co-NP recently. I know that UNSAT $\in$ co-NP. So I want to find more examples of UNSAT, especially about 3CNF paradigm.
1 vote
28 views

### Prove that CorrectConnSolver is coNP-Complete

I need to prove that CorrectConnSolver is coNP-Complete where CorrectConnSolver is defind as follows: CorrectConnSolve$= \{C | C(G) = 1 \iff G$ is connected$\}$. In other words, the ...
510 views

### Why are $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ compatible?

If $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ are both true then $\sf{P}$, $\sf{NP}$ and $\sf{coNP}$ are three separate complexity classes. In other words, verifying a solution, finding a ...
41 views

157 views

### How does a co-NP problem differ from an NP (its complement) one?

I have quite a hard time understanding co-NP problems. If we can reduce every problem to decision problem. NP problems should accept YES instances -> instances where the answer is yes. So for example ...
1 vote
313 views

### Understanding Hamiltonian Path, NP vs Co-NP

I am having difficulty understanding the distinction between NP and Co-NP. According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language: HAMPATH = { (G,s,t) | G is a ...
1k views

### Is this a correct way to show that a problem is coNP-complete?

Let $A$ be a problem that I want to show it is coNP-complete. I know I could just show its complement $\bar{A}$ is NP-complete or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show ...
1 vote
65 views

### Give a Search Problem in co-NP

Ex.1. Give a Search Problem whose deciding Problem is in co-NP. Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right? Then would asking ...
1 vote
255 views

### Necessity to define co-NP in the first place?

I've recently started to deal with complexity theory and I'm trying to wrap my head around all the definitions and why they make sense. One thing I don't quite understand is the importance/necessity ...
1 vote
211 views

### Prove EXPTIME \ NP is not a subset of NP-Hard?

If we assume that NP is not equal to co-NP, how do we show that EXPTIME \ NP is not a subset of NP-Hard?
1 vote
146 views

### On importance of Stockmeyer theorem

Theorem: (Stockmeyer, 1974) Any circuit that takes as input a formula (in the language of WS1S) with up to 616 symbols and produces as output a correct answer saying whether the formula is valid ...
171 views

### Complete problems in NP∩coNP

I often read in Complexity literature that NP∩coNP is unlikely to have any complete problems. Is that unlikelihood "proved" ? By proved, I mean that there would be a theorem that would relate the ...
111 views

### Isn't NP problems always also co-NP problems?

I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every ...
67 views

### "Insensitive" CNF/DNF SAT always satisfying same number of clauses

I came across this paper, which mentions an interesting variation on SAT: We call a CNF formula F insensitive if every total assignment α satisfies the same number of clauses of F. I hadn't come ...
8k views

### Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)

I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every ...
1k views

### Why isn't coNP = NP? [duplicate]

I am having trouble understanding the class $coNP$. We defined $$coNP = \left\{ \overline{A} : A \in NP \right\}$$ As far as I know, a language $A$ is in $NP$ if, and only if, a non-deterministic ...
1 vote
1k views

### How do I prove that SAT in coNP implies NP=coNP?

Is it true that if SAT is in coNP then its also coNP-complete (because it is NP-complete)?
1 vote
554 views

### Showing a problem is in coNP

We have the problem $C = \{<G,S>| \text{ S is a minimal cover of G }\}$ and we want to show that $C\in coNP$. I can easily show that there's a ND TM that decides $coC$ using a guess to check if ...
2k views

### co-NP but not NP problems

What are the problems that are in co-NP but not in NP? i.e, those problems where incorrect strings can be deterministically verified in polynomial time but the correct strings can't be.
695 views