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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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.
user avatar
  • 153
1 vote
0 answers
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 ...
user avatar
  • 23
5 votes
1 answer
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 ...
user avatar
  • 683
2 votes
1 answer
41 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 }...
user avatar
  • 165
1 vote
2 answers
73 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 ...
user avatar
  • 153
4 votes
1 answer
205 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 ...
user avatar
  • 145
2 votes
0 answers
38 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 ...
user avatar
1 vote
1 answer
33 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)$, ...
user avatar
  • 13
1 vote
0 answers
18 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 ...
user avatar
  • 11
0 votes
0 answers
32 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 ...
user avatar
  • 11
1 vote
1 answer
62 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"?
user avatar
0 votes
0 answers
58 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 $...
user avatar
  • 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, ...
user avatar
  • 23
3 votes
3 answers
890 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 ...
user avatar
  • 31
0 votes
1 answer
294 views

is co-NP-hard contained in EXPTIME-hard or vice-versa?

is co-NP-hard contained in EXPTIME-hard or vice-versa?
user avatar
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"...
user avatar
  • 29
-1 votes
1 answer
145 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 ...
user avatar
  • 29
0 votes
3 answers
66 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 (...
user avatar
  • 683
1 vote
1 answer
69 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....
user avatar
0 votes
1 answer
460 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 ...
user avatar
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.
user avatar
  • 121
1 vote
1 answer
34 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 ...
user avatar
  • 1,035
-1 votes
2 answers
192 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 ...
user avatar
  • 1,035
1 vote
2 answers
226 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 ...
user avatar
0 votes
0 answers
138 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?
user avatar
  • 2,824
0 votes
1 answer
95 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$?
user avatar
2 votes
1 answer
256 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 ...
user avatar
  • 313
0 votes
0 answers
70 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 ...
user avatar
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_{...
user avatar
  • 13
0 votes
2 answers
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 ...
user avatar
  • 179
1 vote
2 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 332
1 vote
1 answer
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
1 vote
1 answer
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?
user avatar
  • 11
1 vote
1 answer
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
  • 352
0 votes
2 answers
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 ...
user avatar
  • 143
3 votes
1 answer
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 ...
user avatar
8 votes
1 answer
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 ...
user avatar
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 ...
user avatar
1 vote
1 answer
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)?
user avatar
  • 11
1 vote
1 answer
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 ...
user avatar
  • 313
2 votes
2 answers
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.
user avatar
3 votes
2 answers
695 views

Does integer programming $\in$ NP imply $NP=CoNP$?

Although it is relatively simple to see that integer linear programming is NP-hard, whether it lies in NP is a bit harder. Therefore, I'm wondering whether the following reasoning shows that $ILP\in ...
user avatar
  • 6,978
1 vote
1 answer
555 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 ...
user avatar
0 votes
1 answer
190 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:...
user avatar
  • 127
4 votes
0 answers
127 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 ...
user avatar