Linked Questions

0
votes
1answer
1k views

If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

In my super non-rigorous class on optimization, the prof defined NP as the class of decision problems that cannot be solved in polynomial time. By definition, P is the class of decision problems that ...
0
votes
0answers
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 ...
3
votes
1answer
156 views

Any suggestions about a known NP-complete problem that can be reduced to the following problem?

Given an undirected graph $G$, where nodes represent towns and edges represent roads, and given a positive integer $k$, is there a way to build $k$ McDonald's at $k$ different towns so that every town ...
1
vote
3answers
162 views

"Equivalent device" for testing for NP and coNP?

I'm trying to understand some aspects of the $P=^?NP$ and $NP=^?coNP$ problems. I am engineer and not mathematician nor computer scientist so I do not completely understand what a turing machine is. ...
3
votes
2answers
640 views

Mapping graph to another graph's sub-graph

How to solve the induced sub-graph isomorphism problem?
0
votes
0answers
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 ...
0
votes
1answer
269 views

Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?

Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a ...
1
vote
1answer
129 views

Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can ...
0
votes
0answers
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 ...
7
votes
1answer
2k views

Why is determining if there is a solution to a Battleship puzzle NP-Complete?

This paper http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf says that the decision problem, "Given a particular puzzle, is there a solution?" is NP-Complete. I don't ...
0
votes
1answer
698 views

Would a polynomial-time algorithm for an NP-hard problem implies that P=NP? [duplicate]

An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.) So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would ...
5
votes
2answers
3k views

Can all NP-hard problems be reduced to one another?

I know that all NP-complete problems can be reduced to each other, but how about NP-hard problems? Can all NP-hard problems be reduced to one another?
3
votes
1answer
609 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after <...
1
vote
1answer
43 views

NP-Completeness: A question about reduction and hardness [duplicate]

I am trying to understand the definition / meaning of reduction. Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For ...
1
vote
1answer
137 views

Does exponentiation reduce to multiplication or the other way around?

Is is more accurate to say that in complexity theory: $$\text{exponentiation} \leq_p \text{multiplication}$$ or $$\text{multiplication} \leq_p \text{exponentiation}$$ I understand that if we know ...

15 30 50 per page
1
3 4
5
6 7
9