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 ...
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......
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 ...
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 ...