Skip to main content
Computer Science

Questions tagged [co-np]

Ask Question

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.

78 questions
Newest Active Bountied Unanswered
0 votes
1 answer
92 views

I have a problem with the following specs: The input is a permutation of size $n$. The search space is a poset where the size could be up to $\left(\frac{n}{4}\right)!^2$ (or possibly larger, but I ...
Matt Samuel's user avatar
  • 133
0 votes
1 answer
117 views

If $L\subseteq \{0, 1\}^∗$ is a language, then we denote by $\overline{L}$ the complement of $L$. That is, $\overline{L} = \{0, 1\}^∗\setminus L.$ We make the following one definition of $\mathrm{...
Redbull's user avatar
  • 43
0 votes
1 answer
81 views

Under the assumptions $\text{NP} \neq \text{coNP}$ and $\text{P}\neq\text{NP}\cap \text{coNP}$, we need to prove that there is a language $L$ that satisfies the following: $L\notin \text{P}$. $L\in \...
Dee's user avatar
  • 141
4 votes
1 answer
272 views

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 ...
OE.omergunr100's user avatar
  • 43
1 vote
1 answer
479 views

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?
Naneless's user avatar
  • 21
0 votes
0 answers
124 views

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

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

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
  • 6,131
0 votes
1 answer
121 views

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

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
  • 11
0 votes
1 answer
81 views

$\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
  • 147
0 votes
1 answer
174 views

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
  • 1
0 votes
0 answers
108 views

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
  • 9
2 votes
1 answer
174 views

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

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
  • 317

15 30 50 per page
1
2 3 4 5 6