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
-1
votes
1answer
21 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 ...
0
votes
0answers
63 views

Exact2IS - Question

I have the following question for Exact2IS problem that is defined: $$ \mathrm{Exact2IS} = \{(G,k) \mid \text{$G$ contains exactly two independent sets of size $k$}\}. $$ and I would like to know ...
0
votes
3answers
35 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 (...
1
vote
1answer
38 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....
0
votes
1answer
97 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
0answers
21 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.
1
vote
1answer
20 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
votes
2answers
77 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
vote
2answers
72 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 ...
0
votes
0answers
46 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?
0
votes
1answer
63 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$?
2
votes
1answer
63 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 ...
0
votes
0answers
47 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 ...
1
vote
1answer
49 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_{...
0
votes
2answers
89 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
2answers
108 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 ...
2
votes
1answer
557 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
1answer
59 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
2answers
107 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
1answer
170 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
1answer
100 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 ...
3
votes
0answers
151 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 ...
0
votes
2answers
56 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 ...
3
votes
1answer
48 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 ...
7
votes
1answer
5k 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 ...
0
votes
1answer
942 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
1answer
637 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
1answer
323 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 ...
2
votes
2answers
1k 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.
3
votes
2answers
543 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 ...
1
vote
1answer
375 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 ...
0
votes
1answer
130 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:...
4
votes
0answers
111 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 ...
0
votes
2answers
123 views

Without primes in $P$ does integer factorization lie in $coNP$?

In integer factorization we ask 'Given $N$ is there a $a\in[2,\sqrt{N}+1]$ such that $a|N$?'. Is the above problem in coNP because we know primes is in $P$? That is there is no such factor $a$ of $...
4
votes
1answer
616 views

An obvious approach to explaining NP != coNP, how far has it been pushed?

A recent question made me think about an obvious approach for circumventing the "algorithm is allowed to do anything" problem, when proving lower bounds. Instead of starting with a simple looking NP-...
3
votes
1answer
166 views

An obvious approach to NP = coNP, is there a counterexample?

Let's try to solve "co3SAT" with an NTM in polynomial time. It seems we need, more or less, to guess a proof that the formula is unsatisfiable i.e. derive a contradiction. We've got a formula in ...
2
votes
1answer
2k views

Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?) [duplicate]

I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble. Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of co-...
0
votes
1answer
196 views

Some questions about NP / coNP / CSP

I need help with the following mock exam questions. True or false? 1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$. True. Every finite set is in $P$ and ...
0
votes
1answer
1k views

Co NP problem correponding to SAT

I've been reading lately about SAT problem, NP and co-NP. Many sources say that the SAT problem is co NP, though, I can't find a co-NP problem equivalent to SAT. Does anyone have any idea about ...
1
vote
2answers
752 views

Is P^SAT with only one query equal to the union of NP and coNP?

I have a following problem: Let $P^{SAT[1]}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle). Assume that: $\mathrm{co}...
1
vote
1answer
597 views

Showing that DNF VALID is coNP-hard

I'm trying to understand/show that DNF VALID is coNP-hard. I have given an algorithm for the complement of DNF VALID and shown that this is in NP (since the complement of a language in NP is in coNP), ...
6
votes
1answer
175 views

Why doesn't a time cutoff convert NP problems into co-NP? [duplicate]

Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations. You make a tweak to the verifier program, so that if it takes more than $f(n)$ ...