# 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
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
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 ...
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 ...
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
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
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 ...
1 vote
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 ...
1 vote
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, ...
1 vote
45 views

1 vote
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 ...
1 vote
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