Linked Questions

1
vote
2answers
273 views

What is the name for polynomially solvable optimisation problems?

An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known. Symmetrically, ...
52
votes
6answers
14k views

Why are some games np-complete?

I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? ...
0
votes
0answers
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 ...
2
votes
1answer
419 views

How to find subset of vectors whose sum has certain characteristics

Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$: $$ \begin{align*} L_0 &= [1,0,x] \\ L_1 &= [1,1,1] \\ L_2 &= [1,0,0] \\ L_3 &= [x,1,0] \\ L_4 &...
5
votes
1answer
2k views

If X reduces to a problem in NP, is X in NP?

Let $X$ and $Y$ be problems, and let $X \le_p Y$. Is it true that \begin{equation} Y \in NP \rightarrow X \in NP\ ? \end{equation} I do mean $NP$ here, not $NP$-complete or $NP$-hard. The solution ...
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
99 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
158 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
168 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
661 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
275 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
137 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 ...

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