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.
65
questions
1
vote
1
answer
24
views
I would like to know what are the directions to work on if I want to prove that $NP=coNP$?
I am currently learning about NP and coNP related content and have been exposed to the$NP \overset{\text{?}}{=}coNP$ problem.
I would like to know what are the directions to work on if I want to prove ...
- 195
1
vote
1
answer
71
views
Why is 3-co-SAT not in P?
The 3-co-SAT problem consists of deciding whether if a 3CNF formula, has an unsatisfiable assignment of variables, i.e., assignment of variables that evaluates to 0.
We know that 3-co-SAT is in coNP, ...
- 23
1
vote
1
answer
20
views
union of NP and co-NP, closure under polynomial time reduction
Is $Union = NP\cup co-NP$ closed under polynomial-time many-one reductions?
I understand that in order to be so, for $A\in Union, A \leq_P B $ there should exist a polynomial time computable function $...
-1
votes
1
answer
52
views
EXACT INDSET is DP-complete
The class DP is defined as the set of languages L for which there are
two languages $L1 \in NP$ , $L2 \in coNP$ such that $L = L1 \cap L2$. (Do not
confuse DP with $NP \cap coNP$, which may seem ...
- 37
0
votes
1
answer
60
views
Does a language have the same time complexity as its complement language?
If $L ⊆ \{0, 1\}^*$ is a language, then we denote by $ \overline{L}$ the complement of $L$
For example, the definition of $coNP$ is $coNP =\{L | \overline{L} \in NP\}$
The complement of $SAT$ language ...
- 195
1
vote
1
answer
64
views
Are there any known interactive proof protocols for NP-complete problems?
In a 2015 Quanta article talking about a breakthrough in the graph isomorphism problem, it was mentioned that graph isomorphism has a unique property where we have an interactive proof protocol for it....
- 271
0
votes
0
answers
53
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
...
- 113
0
votes
0
answers
43
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 ...
- 35
0
votes
0
answers
23
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.
- 195
1
vote
0
answers
29
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
...
- 23
5
votes
1
answer
527
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 ...
- 673
2
votes
1
answer
56
views
Prove $\text{CorrectSuccintSolver} \in \mathbf{coNP}$
Define the following languages:
$$
\text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in }...
- 165
1
vote
2
answers
93
views
Can you help me provide some examples of 3-co-SAT?
Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable， namely ...
- 195
4
votes
1
answer
470
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 ...
- 145
2
votes
0
answers
39
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 ...
- 494
1
vote
1
answer
36
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)$, ...
- 13
1
vote
0
answers
25
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 ...
- 11
0
votes
0
answers
33
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 ...
- 11
1
vote
1
answer
151
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"?
- 373
0
votes
0
answers
63
views
How can I show a problem is in the intersection of np and co-np using duality and Farkas-lemma?
Currently, I have a hard time to find out the solution to this problem:
Given a matrix $A \in Z^{m \times n}$, $b \in Z^m$, $c \in R^n$ and $\lambda \in R$. Is there $x \in R^n$ with $Ax \leq b$ and $...
- 1
2
votes
1
answer
1k
views
Why does SAT-UNSAT $\in NP \implies NP = coNP$
I was reading this post about the DP completeness of the problem SAT-UNSAT (both are well defined in this post). The answer added a note at the end that states the class complexity DP differs from NP, ...
- 23
3
votes
3
answers
1k
views
Why isn't SAT in coNP?
I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).
But I'm missing why the following machine doesn't turing recognize the complementary of SAT:
Given a ...
- 31
0
votes
1
answer
347
views
is co-NP-hard contained in EXPTIME-hard or vice-versa?
is co-NP-hard contained in EXPTIME-hard or vice-versa?
- 1
0
votes
0
answers
21
views
how to prove that $NP \cap co - NP$ = { S | S such that there exist a Strong Deciding Algorithm for S}?
i need to prove that and i find it struggle:
given:
for deciding problem S:
a non deterministic algorithm $A(x)$ is strong deciding algorithm if:
$x \in S =>$ fo every run of $A(x)$ returns "Yes"...
- 29
-1
votes
1
answer
168
views
Close To Cook Reduction given NP != coNP
I am struggling to answer these two questions:
Prove or wrong:
Both are given the assumption that NP != coNP.
For any 2 decision problems S, S', if there is a Cook reduction from S' to S then there ...
- 29
0
votes
3
answers
82
views
Is it possible that Co-NP = P but NP != P
Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (...
- 673
1
vote
1
answer
74
views
Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time?
Goldbach's Conjecture says every even integer $>$ $2$ can be expressed as the sum of two primes.
Let's say $N$ is our input and its $10$. Which is an integer > 2 and is not odd.
Algorithm
1....
- 57
0
votes
1
answer
545
views
Show that NP∩coNP =∅
I know that P is a subset of NP, but I'm not sure what this tells me about P as it relates to coNP?
I feel like this is how I should go about proving it, but I'm not sure how. Otherwise, I could find ...
2
votes
0
answers
23
views
Flip Output of SAT problem [duplicate]
Why cant I Just create a TM A that runs a NTM B with a formula to compute the SAT Problem and Just Flip its Output. So when the Input NTM B Returns true (formula is satisfyable) the TM A Return false.
- 121
1
vote
1
answer
41
views
Need clarification regarding certificates of coNP problems
NOTE: this is not an attempt to prove $NP \neq coNP$
There is one thing I have never been able to completely digest about the certificates of problems in $coNP$ and I would very much appreciate a ...
- 1,043
-1
votes
2
answers
241
views
A question about NP and coNP
It is an open question if NP $\neq$ Co-NP but if the conjecture were proved, this would mean that P $\neq$ NP
because P is closed under complement.
Now a fact that fails to enter my head is the ...
- 1,043
2
votes
2
answers
276
views
Complement of languages and coNP
By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.
$L^c$ is said to be the complement of the language, and it seems to be ...
- 217
0
votes
0
answers
148
views
Intersection of decision problems?
Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
- 2,844
0
votes
1
answer
101
views
Are there any "complete" languages in $coNP -NP$?
Suppose $coNP \neq NP$
language B would be called "complete" in $coNP-NP$ if:
$B\in coNP - NP$
$A\in coNP-NP \implies A\leq_pB$
Are there any "complete" languages in $coNP - NP$?
user99674
2
votes
1
answer
330
views
Decision variation of max sat
I am trying to prove that following decison variation of MaxSAT is both NP hard and co-NP hard.
$(\phi ,k) \in L$ iff an assignment of $\phi$ satisfies k clauses and no assignment satisfies more than ...
- 313
0
votes
0
answers
78
views
Reduction of complement from complexity class co-np and p
Let P $ \neq $ NP.
D is in the complexity class co-NP.
B is in the complexity class P.
Let $ \bar{D} $ be the complement of D, then $\bar{D} $ $\leq _ {p} $ B.
Is this statement true or false? My ...
user101036
1
vote
1
answer
54
views
How to show that this decision problem is in co-NP?
Given a set of strictly positive numbers $a_1, ..., a_n$, the problem is to determine if $\lfloor n/2 \rfloor$ different indexes $i_1, ..., i_{\lfloor n/2 \rfloor}$ exist so that $$\frac{a_{i_j}}{a_{...
- 13
0
votes
2
answers
220
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 ...
- 179
1
vote
2
answers
352
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 ...
- 27
2
votes
1
answer
2k
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 ...
- 332
1
vote
1
answer
66
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 ...
- 209
1
vote
2
answers
270
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
1
answer
216
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?
- 11
1
vote
1
answer
160
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 ...
- 484
3
votes
0
answers
172
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 ...
- 362
0
votes
2
answers
132
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 ...
- 143
3
votes
1
answer
72
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 ...
- 700
8
votes
1
answer
10k
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 ...
- 257
0
votes
1
answer
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 ...
- 257
1
vote
1
answer
2k
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)?
- 11