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

learn more… | top users | synonyms

1
vote
0answers
38 views

prove that the satisfiability problem with each clause containing at most 3 literals, denoted by ≤3SAT, is NP-complete

I've tried to prove it for several days but I can't make sure if it is equivalent to max-3-SAT problem? This problem seems similar to the proof of SAT ∝ 3-SAT except the case where there are more than ...
6
votes
1answer
107 views

Are there any known lower-bounds for complexity on Non-determinsitic machines

For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time. Are they any problems where we have known lower bounds for ...
1
vote
0answers
42 views

Why do we need cook reductions?

I have a question about cook reductions and karp reductions. Which is the stronger form? As a cook reduction reduces a search problem to a decision problem which can then be reduced using karp ...
-1
votes
0answers
49 views

Prove that if X is in NP and Y reduces to X, then Y is also in NP

Prove that if X ∈ NP and Y ≤p X, then Y ∈ NP I'm having so trouble with how to go about this proof. I think the steps are to say that X is in NP, and Y reduces to X, therefore if we can solve X, we ...
2
votes
2answers
97 views

How are games like chess provably harder than NP?

From this question, I had the debate about how problems harder than NP are proved. I said that intuitively I understand it as (from this video explaining that some problems are provably harder than ...
0
votes
0answers
25 views

If problems P1 and P2 are known to be NP-hard, then we can conclude that P1∝P2 and P2∝P1? [duplicate]

I know the definition of NP-hard is that “a problem(P1 or P2) is NP-hard if every NP problem could be polynomially reduce to (P1 or P2)”. However, P1∝P2 means P1 could be polynomially reduced to P2, ...
3
votes
2answers
325 views

What complexity class would this version of generalized chess fall?

By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof ...
3
votes
1answer
33 views

How does (non)deterministic time relate to verifiability?

So far, from all the research I've done, I've come across 2 different ways that NP time is explained. One is that a nondeterministic turing machine is able to solve the problem in polynomial time. It ...
3
votes
1answer
41 views

Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?

I'm curious if we can reduce an $NP$-complete problem to an $NP$ problem which is not a part of the $P$ set. Meaning, can we take an algorithm for this kind of $NP$ problem and use it to solve a ...
5
votes
1answer
182 views

How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
6
votes
1answer
103 views

Is EXPTIME “solvable” or “checkable” in exponential time?

According to this video, EXP has problems that are exponentially difficult to check. But according to this video, EXP are problems that are exponentially difficult to solve. It would make sense to ...
0
votes
1answer
34 views

How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?

I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP. I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N ...
7
votes
2answers
257 views

An one-sentence proof of P ⊆ NP

Recently I am reading a document [1]. In this document, Prof. Cook provides a brief proof of $\mathbf{P} \subseteq \mathbf{NP}$, which is only one sentence: It is trivial to show that $\mathbf{P} \...
1
vote
1answer
35 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?
3
votes
2answers
78 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 ...
4
votes
1answer
65 views

Known problems in BQP \ NP?

The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\...
0
votes
0answers
41 views

Is a problem in NP if it is decided by some non-deterministic, polynomial time turing machine? [duplicate]

I am working trough the book "Introduction to the theory of computation", 3rd edition, by M. Sipser. On page 294, the book states: A problem is in NP iff it is decided by some non-deterministic, ...
1
vote
1answer
85 views

Why IS is not in NL, only in NP?

All we need to do is guess $k$ vertices. We look at vertex $v_1$, and make sure $v_1$ is not connected to $v_2...v_k$. Then, we "throw" $v_1$, and look at $v_2$. We do this to all vertices. Meaning ...
11
votes
3answers
846 views

Can any finite problem be in NP-Complete?

My lecturer made the statement Any finite problem cannot be NP-Complete He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of ...
1
vote
0answers
85 views

If NP is easy on average then does it mean P=NP?

If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have $NP=RP\...
0
votes
1answer
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:...
1
vote
1answer
78 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 ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
3
votes
0answers
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$ ...
1
vote
0answers
19 views

A question about SOS duality

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 ...
3
votes
1answer
37 views

How to find a perfect matching with this constraint?

I have a positive integer $n$ and two disjoint sets of nodes $V=\{v_1,\ldots,v_n\}$ and $W=\{w_1,\ldots,w_n\}$. I also have a weight function $f:V\times W\to\mathbb{R}_{>0}$ and a positive number $\...
4
votes
2answers
63 views

On certificates in BPP (avoiding majority vote)

Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output. However if the problem $\Pi$ is also in $NP$ ...
2
votes
1answer
31 views

Is a degree-$d$ pseudo distribution always a relaxation?

The optimization problem we are generally concerned with looks like the following, \begin{eqnarray*} &\inf \{ p(x) \vert x \in K\} \\ &K = \{ x \in \mathbb{R}^n \vert q_i(x) \geq 0, i = 1,..,m ...
4
votes
1answer
528 views

Give a specific case where calling a polynomial time function n times gives an exponential time algorithm

We were asked this question in exam and I am not satisfied with the answer the teacher gave. Let me justify my point of view. Let there be a polynomial time function having time complexity $n^{c_1}$. ...
3
votes
1answer
139 views

About the notation of XOR-SAT

I am a bit confused by the notation here, http://www.boazbarak.org/sos/files/lec3.pdf Given 3 Boolean variables $x_i, x_j, x_k$ what is supposed to be the meaning of $x_i \oplus x_j \oplus x_k$? ...
0
votes
0answers
15 views

Want to show that if P = NP, then P = NP = CoNP [duplicate]

I want to show that if P = NP, then P = NP = CoNP. Essentially, I want to show that if the set of problems which can be solved in polynomial time is exactly the set of problems which can be checked in ...
4
votes
1answer
74 views

See that P$^{NP}_{||} = P^{NP}_{O(\log n)}$

I'm trying to prove that P$^{NP}_{||} =$ P$^{NP}_{O(\log n)}$ where $n$ is the length of the input. So, to see that polynomially many non-adaptive queries to a problem in NP can do as much as ...
2
votes
1answer
28 views

A certain submatrix of the correlation polytope

I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf Firstly given that the author wanted to look at quadratic ...
0
votes
1answer
61 views

Would a polynomial-time algorithm for an NP-hard problem implies that P=NP? [duplicate]

An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.) So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would ...
1
vote
2answers
44 views

Proof that MAX CLIQUE is NP-Hard

My question is simple: does any body know where can I find the proof that MAX CLIQUE is NP-HARD? Remarks: MAX CLIQUE is the decision problem defined as follows:Given a graph $G$ and $k>0$. Does ...
1
vote
1answer
16 views

Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?

Lets say one is given a set of $m$ real polynomial equations in $n$ variables, $P_1 = P_2 = P_2 .. = P_m =0$. I understand that there is some theorem which says that if there is no solution to these ...
0
votes
0answers
73 views

How not to prove that P ≠ NP implies NP ≠ PSPACE

Let's define the two variants of the Travelling salesmen problem: $TSP_{opt}$ : Give me the shortest tour $TSP_{dec}$ : Is there a tour of $l$ or shorther (Yes/No) Now assume $P \neq NP$: Since $...
7
votes
1answer
407 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 ...
2
votes
1answer
89 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$ ...
-1
votes
1answer
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, ...
0
votes
0answers
36 views

What is an example of a problem that is in NP - P, but not NPC? [duplicate]

Assuming $P \neq NP$, I expected that $NP - P \subset NPC$, but from the diagram on Wikipedia it appears to not necessarily be true. What is an example of a problem that is complex enough to be in $...
3
votes
1answer
91 views

Proof that this problem is in NP

I have to prove the following problem is in NP (and define verifier as well as the certificate/witness): The input is a set of $n$ boxes with weights $w_{1},\ldots,w_{n}$ and two numbers $s$ and $t$ ...
4
votes
1answer
450 views

An obvious approach to explaining NP != coNP, how far has it been pushed?

A recent question made me think about an obvious approach for circumventing the "algorithm is allowed to do anything" problem, when proving lower bounds. Instead of starting with a simple looking NP-...
3
votes
1answer
113 views

An obvious approach to NP = coNP, is there a counterexample?

Let's try to solve "co3SAT" with an NTM in polynomial time. It seems we need, more or less, to guess a proof that the formula is unsatisfiable i.e. derive a contradiction. We've got a formula in ...
-2
votes
2answers
86 views

How to prove P ⊆ Co-NP

My approach Let L ∈ P $\exists$ Turing Machine $M_1$ which decides L. We can easily construct $M_2$ which decides $\bar{L}$ $\bar{L}$ ∈ CO-NP $\implies$ P ⊆ Co-NP I'm not sure ...
5
votes
1answer
63 views

Certificates and NP?

My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be. For instance, for SAT, ...
0
votes
0answers
21 views

Why does not the complement of a language belonging to class NP, also belong to NP in general? [duplicate]

I know that complement of a language belonging to NP, does not necessarily belong to NP. I came across the example $L= \{\langle G,s,t \rangle | G \text{ is a directed graph and there exists a ...
1
vote
1answer
67 views

NP to SAT. How does it works? [closed]

Let's start here: It is said that all NP problems can be reduced to SAT(boolean satisfiability problem). To be more accurate to Circuit SAT, because all decision problems like NP should end up with ...
2
votes
1answer
246 views

Why do puzzles like Masyu lie in NP?

The puzzle is made up of (n x n) squares so when taking the problem the input size would be n. Rules of Masyu: The goal is to draw a single continuous non-intersecting loop that properly passes ...