The 2024 Developer Survey results are live! See the results

# 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.

77 questions
Filter by
Sorted by
Tagged with
62 views

### Is there any consensus as to Gordeev & Haeusler's purported proof of $\mathsf{NP} = \mathrm{co}\mathsf{NP}$?

As title states, I'm interested in knowing whether there is any known consensus as to Gordeev and Haeusler's recent results claiming $\mathsf{NP} = \mathrm{co}\mathsf{NP} = \mathsf{PSPACE}$. Although ...
• 165
24 views

### If A ∈ coNP, B ∈ NP and $NP \neq coNP$, is it possible to Karp reduce A to B?

If A $\geq_p$B and $B\in NP$, $A\in coNP$, then we can build a Turing machine $M_A$ using $M_B$ machine of B. Input: w We make a new word with a reduction function $f(w)$. Then we run $M_B$ on $f(w)$ ...
• 21
224 views

### Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

As the title states, I need to prove that the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard. I'm not looking for a solution but a clue or something to help me ...
1 vote
396 views

### If coNP ⊆ NP, does that mean coNP = NP?

I had an exam, and one of the questions was Does ZPP = BPP if coNP ⊆ ZPP. I came down to coNP ⊆ NP and went on with "then coNP = NP", am i right?
• 21
90 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 ...
• 321
57 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 ...
• 243
141 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. ...
• 6,132
67 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 ...
• 93
1 vote
74 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 ...
37 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
111 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
69 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
111 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
52 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 ...
• 315
1 vote
86 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
108 views

• 13