Linked Questions

0
votes
1answer
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 ...
0
votes
0answers
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 ...
-2
votes
1answer
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 ...
2
votes
3answers
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}$?
2
votes
2answers
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 ...
2
votes
1answer
142 views

Proof of NP-completeness via extra information

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \...
-2
votes
2answers
115 views

Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)

Let me explain my trouble by another example. The wiki page says that Lattice problems are an example of NP-hard problems However, by clicking NP-hard, i find this definition A decision problem H ...
0
votes
0answers
20 views

Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?

I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
2
votes
2answers
50 views

Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem

I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following: There exists a believed-today NP-hard problem ...
0
votes
1answer
95 views

Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?

This relates to an answer for this question. The opinion said that: Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most ...
1
vote
0answers
25 views

are all problems in P in NP [duplicate]

I know this is a similar question to this post, but I want to further clarify my understanding. In the picture from wikipedia: I understand that every problem that's in $P$ is also in NP. does this ...
-1
votes
3answers
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 ...
2
votes
2answers
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 ...
0
votes
2answers
104 views

Is P contained in NP-hard?

I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me. NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained ...
1
vote
1answer
85 views

Reframing decision, counting, enumeration, and search as optimization

The top accepted answers to the questions below allude to two complexity classes of optimization problems: NPO and PO (in relation to NP and P for decision problems): Decision problems vs "real" ...

15 30 50 per page
1
2 3 4 5
9