# 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.

53 questions
Filter by
Sorted by
Tagged with
79 views

### Is 3-UNSAT problem coNP-complete?

The 3-SAT problem, i.e. the problem whether a given Boolean formula consisting of clauses of at most 3 literals is known to be NP-complete. Then it’s complement, i.e. whether such a formula is ...
29 views

### How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?

Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get? So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
26 views

### If $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$?

Is it true that if $S\in\left(NP\bigcup coNP\right)$ then $\overline{S}\in NP\bigcap coNP$? I couldn't find any answer to that question. My attempt at proving it: If $S\in\left(NP\bigcup coNP\right)$, ...
14 views

### What is the difference between NP and co-NP? [duplicate]

I'm trying to understand the very simple concept of co-NP but I can't figure it out. On wikipedia, it gives the example of SAT and its complement: The complement of any problem in NP is a problem in ...
30 views

### If a problem A has a poly-time reduction to a problem B in co-NP, is A in co-NP as well?

i.e. $A\leq_pB\:\wedge\:B\in\text{co-NP}\rightarrow A\in\text{co-NP}$ ? I feel like it's the case but I can't think of a straightforward proof. Clarification: I am talking about polynomial-time Turing ...
32 views

### $\overline{SAT}$ vs. $UNSAT$, Is it the same?

I know this question may look stupid, but still.. Is the meaning of both "have no satisfiable assignment"?
27 views

### Reducing co-NP and NP. (Karp and Turing)

Why is it true that: If every problem in co-NP can be Karp reduced to a problem A, every problem in NP can be Turing reduced to A?
42 views

444 views

### Is Maximum Independent Set in coNP

I need to determine whether the following problem $X$ is in coNP: Given a graph $G=(V,E)$ and a positive integer $s\leq|V|$, is there an independent set that is the largest for $G$ of size at ...
151 views

### Finding the mistake(s) within this "proof" of NP being closed for complement

For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some help:...
121 views

### Interactive proofs for coNP languages proof clarification

I was reading a paper by Lance Fortnow and Michael Sipser. "Are there interactive protocols for co-NP languages?" Information Processing Letters 28 v5 (1988), pp. 249-251. An online version of the ...