15 views

### Understanding P, NP with an example decision problem

I was reading the definitions of p vs np in [this post] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you ...
24 views

### Is Knapsack-optimization problem NP-hard while Knapsack-search problem NP-complete?

I am learning Computational Complexity. Is Knapsack-optimization problem (find an arrangement to maximize the value) known to be NP-hard, while Knapsack-search problem (find an arrangement so that ...
28 views

### What is the difference between NP hard and NP complete?

What is the definition of P, NP, NP-complete and NP-hard? here is a good answer but it really doesn't answer mym question. np-hard-: a problem A is NP hard if for all B$\in$NP, B is polynomial time ...
586 views

### Are there problems in NP that do not reduce in polynomial time to any problem in NP?

As the title says: are there problems in $\mathbf{NP}$ that do not reduce in polynomial time to any problem in $\mathbf{NP}$?
145 views

### determine Eulerian or Hamiltonian

I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions. For eulerian, I can say that the graph has ...
142 views

289 views

### Why don't passwords prove P != NP?

Pardon my ignorance on the matter but, Verifying passwords = Polynomial (linear) Guessing passwords = Exponential Since each guess has nothing to do with one another, exponential time is best possible ...
357 views

### P vs NP and Angle Trisection (serious question)

I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level. My understanding from many popular-level sources (like Scott ...