Linked Questions

0
votes
0answers
30 views

Is there a general form of polynomial reductions in complexity theory? [duplicate]

While reading Sipser, in computability I read about many to one mapping reducibility and Turing reducibility,the latter one being a more general form of reducibility. But in the introductory chapter ...
3
votes
3answers
5k views

What does it mean for a problem to be both NP hard and coNP hard

I have a faint notion of what NP hard is (that a problem is legit difficult 3 SAT for example). I have forgotten what coNP hard, and Wikipedia tells me that the complement of coNP hard is NP hard......
1
vote
1answer
394 views

DFA accepts common strings, reduction to NPcomplete

$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and all of the $M_i$ accept some common string.} \}$ I'm trying to show that B is NP-complete. I know I have to reduce it to ...
0
votes
1answer
101 views

Does classification of a problem also require the algorithm used? [duplicate]

Just learnt that a problem in computer science can be divided into the following categories Polynomial problems NP problems NP hard problems NP complete problems ...
1
vote
1answer
904 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 ...
1
vote
1answer
222 views

Proof that circuit design problem is NP-hard [closed]

I have the following problem, and I want to show that it is NP-hard (or NP-complete). Consider a clause which can have OR and XOR relationship between literals, e.g. $c_1=y_1 \lor y_2 \lor (y_3\oplus ...
-1
votes
1answer
78 views

Notation: $L_R = \{w\#y\space|\space R(w,y)\}$?

What is the set $$L_R = \{w\#y\space|\space R(w,y)\}$$ Specifically what kind of conditional is $R(w,y)$? Also what's the purpose of $\#$? This comes from page 2 of the Clay paper on P vs NP: http://...
1
vote
0answers
75 views

Undecidability of an existential theory

$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$. Some theorems (from https://math.stackexchange.com/questions/1382120/ft-has-undecidable-...
1
vote
2answers
2k views

If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?

I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it ...
0
votes
0answers
44 views

How can I determine whether a problem is NP-Hard [duplicate]

So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case? Suppose I have different groups of people m in a list M= {m1, m2} ...
5
votes
2answers
1k views

Find 8 numbers whose sum is closest to a defined value

I have a file that has a number (a positive integer) on each row. Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible. So, ...
0
votes
0answers
22 views

Place 4 notorious problems into 2 diagrams (one assuming P=NP, and the other one assuming P!=NP) [duplicate]

This diagram is on Wikipedia: On left side we see NP-hard intersecting NP class (assuming P!=NP), on right side we see NP-hard including NP (assuming P=NP) Where should I place the following ...
-1
votes
1answer
1k views

How to prove a Double CNF SAT is in NP [duplicate]

So I've been stuck trying to figure this problem out for a while. I've looked on wikis and all over stack exchange but I'm really stumped. This isn't my best subject, so any sort of explanation would ...
16
votes
3answers
758 views

Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
7
votes
1answer
304 views

Kernels in parameterized complexity

Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say: The kernel of a parameterized problem $L$ is a transformation $(x,k) \mapsto (x',k')$ such that: $(x,k) \...

15 30 50 per page
1
5
6
7 8 9