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.
71
questions
0
votes
1
answer
38
views
Is the class NP closed under complement? (Follow-up)
As a follow up to this question already been asked here, I was wondering - if we supposed that P != NP, would then the following reasoning be correct:
In NP problems we can only verify in poly-time ...
- 11
1
vote
1
answer
41
views
Why is infeasibility of linear programming considered to be an NP problem?
I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
0
votes
0
answers
36
views
SMALL-FACTOR is not NPC. Is the statement true or false?
Given the SMALL FACTOR problem where:
INPUT: an integer N and an integer k
OUTPUT: yes ⇐⇒ N has a prime factor ≤ k.
I know that SMALL-FACTOR problem ∈ in NP ∩ CO-NP.
If it were NP-Complete we would ...
0
votes
1
answer
34
views
Hardness of finding exactly two Hamiltonian cycles in a graph
$\newcommand{\nuSwap}{\nu\textsf{-swap}}$
Two Hamiltonian cycles are different if and only if there is at least one edge they do not share.
Let $L$ consist of all graphs with exactly two Hamiltonian ...
- 129
0
votes
1
answer
66
views
PSPACE≠co-NP?Is the statement true?
Is the statement in question true? how can i prove it formally?
I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE
0
votes
0
answers
67
views
if it were shown that every algorithm that solves SAT must have complexity Ω(n^(log n)) then P≠NP?
Shouldn't this statement be false? To be true the implication should be P=NP or am I wrong?
I can't find a formal proof
2
votes
1
answer
77
views
Is the clique decision problem in co-NP?
Is the clique decision problem in co-NP?
Definitions:
"In the clique decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph ...
- 23
1
vote
1
answer
32
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 ...
- 305
1
vote
1
answer
81
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
45
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
236
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 ...
- 47
0
votes
1
answer
67
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 ...
- 305
1
vote
1
answer
84
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
61
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
...
0
votes
0
answers
59
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 ...
- 45
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
534
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 ...
user102180
2
votes
1
answer
63
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
108
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 ...
- 305
4
votes
1
answer
717
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
38
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
26
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 ...
- 111
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 ...
- 111
1
vote
1
answer
293
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
64
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
2k
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
4
answers
2k
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
452
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
192
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
90
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 (...
user102180
1
vote
1
answer
88
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
618
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
50
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,063
-1
votes
2
answers
261
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,063
2
votes
2
answers
319
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
164
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,881
0
votes
1
answer
110
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
375
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
84
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
294
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
413
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
278
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
227
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
181
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