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

9
votes
3answers
446 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
votes
0answers
17 views

Is Dist − NP ⊆ Avg − P a reasonable stance? [on hold]

It is known that $Dist-NP\subseteq Avg-P\implies P=BPP$. So proving $Dist-NP\subseteq Avg-P$ proves $P=BPP$ which most people believe. Now my problem is if $Dist-NP\subseteq Avg-P$ a reasonable ...
1
vote
0answers
71 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 ...
0
votes
1answer
96 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 ...
1
vote
1answer
59 views

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

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
20 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
97 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
18 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
36 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
61 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
29 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
523 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
136 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
1answer
31 views

Reduce knapsack to problem with {0,1}-Matrix

I'm looking for a problem, where i can reduce the knapsack feasibility problem: $$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \{0,1\}^n$$ to a problem, where i have a matrix ...
0
votes
0answers
14 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
73 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
25 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
58 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
40 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
15 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
68 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
386 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
61 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
34 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 ...
0
votes
0answers
35 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
83 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
312 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 ...
3
votes
1answer
112 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
76 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
61 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
65 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
240 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 ...
4
votes
2answers
386 views

Seems like NP cannot equal coNP by the definition of NP

A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will ...
6
votes
1answer
78 views

What NP decision problems are not self-reducible?

So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of ...
11
votes
2answers
816 views

Is Post Correspondence Problem in NP?

I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input ...
0
votes
0answers
45 views

How to solve a problem that is even hard to approximate?

I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a ...
1
vote
1answer
66 views

How to prove membership of NP [duplicate]

My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're ...
6
votes
2answers
200 views

Is there any strategy to brute force search?

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
4
votes
2answers
79 views

Can NP-Hard be converted to NP?

I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem. Can an NP-Hard problem ...
4
votes
3answers
1k views

Evolving artificial neural networks for solving NP problems

I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. ...
2
votes
2answers
108 views

Why is $P \subseteq NP$?

The Clay paper gives a short proof on this in page 2: http://www.claymath.org/sites/default/files/pvsnp.pdf However, Where does it come from that these are inclusive sets and not separate? Or that ...
-2
votes
1answer
60 views

Show that $L^c$ is also in NP

Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below. L is in NP and for every n, there is exactly one string of length n that belongs ...
4
votes
0answers
111 views

If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?

I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure. Begin with $NP \subseteq BQP$ (*) $\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = ...
1
vote
0answers
50 views

Complexity lower bounds via Cook reductions

Karp reduction (polynomial-time many one) is used in complexity theory to define NP-completeness. However, Cook reductions (polynomial-time Turing) is more powerful and intuitive from information ...
1
vote
1answer
84 views

Half-SAT intractability proof

I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution. The problem is as follows: Half-SAT is a problem where C is a CNF boolean ...
10
votes
1answer
241 views

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets: If the set resulting from the union, intersection, or Cartesian product of two ...
11
votes
1answer
315 views

Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
2
votes
1answer
98 views

How are these problem variants that ask about the size of optimal solutions in NP?

I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here. On page 5 (23 in the pdf), it says that the following decision problems are in NP: Is the ...