Linked Questions

7
votes
1answer
3k views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
2
votes
2answers
127 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 ...
1
vote
1answer
135 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 \...
29
votes
5answers
10k views

“NP-complete” optimization problems

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
-2
votes
2answers
109 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
79 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
257 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 ...
4
votes
2answers
297 views

Is it necessary for NP problems to be decision problems?

Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems ...
2
votes
2answers
356 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
96 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
70 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" ...
10
votes
2answers
5k views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...

15 30 50 per page
1
2 3 4 5
9