Skip to main content

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
73 views

Is deciding all combinations of repeated usage of $A$ does not sum up to $A$ coNP-complete?

Given a set $A \subseteq \{1,2,3,\dots\}$, decide if $\sum_{x \in A} x \neq \sum_{y \in B} y$ for every $B$ that is a combination with repeated usage of $A$. We define $B$ to be a combination with ...
The T's user avatar
  • 321
2 votes
1 answer
53 views

How to interpret Universal Quantifier in Alternating Turing Machines?

I am trying to read about Alternating Turing Machines (ATM) that have both existential and universal quantifiers for all their internal states. Given that these models are conceptual, I tend to ...
Zee's user avatar
  • 243
3 votes
2 answers
120 views

Proof that $NP \cap coNP = P$

Suppose I want to prove that $NP \cap coNP = P$. Since clearly $P\subseteq NP \cap coNP$, I need to prove the opposite direction, i.e., every problem in $NP \cap coNP$ has a polynomial-time algorithm. ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
58 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 ...
Meki21's user avatar
  • 93
1 vote
1 answer
54 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 ...
Namrata Banerji's user avatar
0 votes
0 answers
43 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 ...
user161646's user avatar
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 ...
tomashauser's user avatar
0 votes
1 answer
90 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
user161390's user avatar
0 votes
0 answers
68 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
PatrickBateman's user avatar
2 votes
1 answer
102 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 ...
Lilith's user avatar
  • 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 ...
lz9866's user avatar
  • 315
1 vote
1 answer
84 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, ...
Denizalp's user avatar
1 vote
1 answer
84 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 $...
obolenskaya00's user avatar
-1 votes
1 answer
285 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 ...
Hjm's user avatar
  • 47
0 votes
1 answer
69 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 ...
lz9866's user avatar
  • 315
1 vote
1 answer
111 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....
user918212's user avatar
0 votes
0 answers
67 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 ...
Benicio Agüero's user avatar
0 votes
0 answers
62 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 ...
Prometheus's user avatar
1 vote
0 answers
30 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 ...
ORN's user avatar
  • 23
5 votes
1 answer
535 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
2 votes
1 answer
70 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 }...
Dennis's user avatar
  • 165
1 vote
2 answers
112 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 ...
lz9866's user avatar
  • 315
4 votes
1 answer
903 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 ...
Gorid's user avatar
  • 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 ...
Dan D-man's user avatar
  • 514
1 vote
1 answer
41 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)$, ...
iii2's user avatar
  • 13
1 vote
0 answers
27 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 ...
nc404's user avatar
  • 111
0 votes
0 answers
35 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 ...
nc404's user avatar
  • 111
1 vote
1 answer
375 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"?
ChaosPredictor's user avatar
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 $...
Jolis's user avatar
  • 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, ...
Exeloz's user avatar
  • 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 ...
wamitw's user avatar
  • 31
0 votes
1 answer
499 views

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

is co-NP-hard contained in EXPTIME-hard or vice-versa?
34r05345's 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"...
Neo182's user avatar
  • 29
-1 votes
1 answer
216 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 ...
Neo182's user avatar
  • 29
0 votes
3 answers
99 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
1 vote
1 answer
92 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....
Dingle Berry's user avatar
0 votes
1 answer
732 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 ...
akshaychacko's 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.
hadamard's user avatar
  • 121
1 vote
1 answer
57 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 ...
Yamar69's user avatar
  • 1,073
-1 votes
2 answers
285 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 ...
Yamar69's user avatar
  • 1,073
2 votes
2 answers
352 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 ...
ramseysdream111's user avatar
0 votes
0 answers
170 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?
Turbo's user avatar
  • 2,891
0 votes
1 answer
113 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
387 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 ...
Root's user avatar
  • 313
0 votes
0 answers
86 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
56 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_{...
Baskoa's user avatar
  • 13
0 votes
2 answers
337 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 ...
trolkura's user avatar
  • 179
1 vote
2 answers
459 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 ...
comp_sci5050's user avatar
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 ...
RTK's user avatar
  • 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 ...
simplesystems's user avatar