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, ...
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? ...
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 ...
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 &...
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 $$Y \in NP \rightarrow X \in NP\ ?$$ I do mean $NP$ here, not $NP$-complete or $NP$-hard. The solution ...
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 ...
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 ...
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 ...
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. ...
661 views

Mapping graph to another graph's sub-graph

How to solve the induced sub-graph isomorphism problem?
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 ...
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 ...
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 ...