Tagged Questions

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

21 views

36 views

CFL that runs in NP-time

What is an example of a context-free language that runs in NP-time? I've done searches but cant find one. Frankly, I do not know how to determine when a CFL is P or NP. Can someone tell me, please?
79 views

NP problems with exponentially complex average time solution?

Assuming $P \ne NP$, is there a problem such that is NP such that: There is always a solution Alternatively, there is asymptotically almost surely a solution On average, it takes exponential time ...
68 views

98 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:...
80 views

How to use an algorithm to find a satisfying assignment in polynomial time? [duplicate]

I am currently trying to solve the following problem but I am unsure how to go about it. The problem states: Suppose that someone gives you a polynomial-time algorithm to decide 3-SAT. Describe how ...
21 views

About the interpretation of the SOS hardness results of the planted Max-Clique problem

One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then both these papers are talking of the ...
101 views

Implication of Berman and Hartmanis conjecture

I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture : All $NP$-Complete languages are $p$-isomorphic. Then the book says that ...
20 views

A particular type of SOS hardness proof

Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical $x_i^2 =1$ ...
20 views

Let us start with the optimization question, \begin{eqnarray*} min \{ c \vert c - f \in SOS_d \} \end{eqnarray*} for some function $f : \{0,1\}^n \rightarrow \mathbb{R}$ and $SOS_d$ being the cone ...
37 views

413 views

How can I show that the Cook-Levin theorem does not relativize?

The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) : Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not ...
91 views

How do I prove Berman's theorem?

Berman's theorem states If a unary language ( a language with all the strings of the type $1^i$, $i > 0$ ) is NP-Complete then P = NP. I tried reducing SAT to a given unary language $L$ ...
37 views

Is the complement of the given language necessarily in NP?

$A$ is a given language so that $A \in NP$. Assume that $P = NP$. Is $A'$ necessarily in NP? What I did: $A \in NP , P=NP$ $P=coP$ (Can be proven by running a TM $M$ as a decider for P, ...
36 views