43 views

### Confusion about P versus NP [duplicate]

I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
32 views

### Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? [duplicate]

Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard?
37 views

### Prove the language L of all palindromes over {0,1} is in NP

Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?
21 views

### NP hardness - Why is one harder than the other? [duplicate]

As far as my understanding goes, to show that a problem A is NP-hard, we use another NP-complete problem B. We reduce (in polynomial time) from B to A, i.e. use A to solve B. This shows that A is ...
93 views

### Proving P and NP on problems formulated as languages

To prove that a certain problem is in P we have to give an algorithm that decides or solves it in polynomial time. To prove that a problem is in NP an algorithm must exist so that it can check whether ...
25 views

### NP-Hard for resolving P=NP [duplicate]

Im studing complexity theory and im reading this question on Quora. According to what the guy is saying : if we are able to solve a NP-Hard problem in polynomial time we have prooved that P=NP. But, ...
34 views

### Why some state that Primes is in NP? [duplicate]

Why some books state that Primes is a NP problem if, as a decidibility problem, it can be solved in polynomial time? A simple example: A number can has its primality tested by dividing it by all ...
112 views

### The defining property of problems in NP [duplicate]

I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some ...
29 views

### Is this line from the rational wiki p vs np bit correct? “ A computational problem is considered ”in P [duplicate]

http://rationalwiki.org/wiki/Pseudomathematics#P_vs._NP_problem A computational problem is considered "in P" if an algorithm exists that can solve the problem in "polynomial time" — that is, it's ...
98 views

### Proving NP-completeness in relation to putting items in bins

If I can assume that it is NP-complete to determine whether a set of objects can be packed into 2 bins, how can I prove that it is NP-complete to determine whether a set of objects can be packed into ...
18 views

### Is NP-complete complexity defined in terms of polynomial reductions or polynomial transformations? [duplicate]

How do you know that a decision problem $X$ is NP-complete?, if all other NP-problems polynomially transform to $X$ or if all other NP-problems polynomially reduces (there exist a polynomial time ...
23 views

### what is NP class? [duplicate]

I actually started to read complexity classes of problems. and I know that NP class include P class problems and even more problems call NP-complete ... as many books define NP class as well But I ...
29 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 ...