Hot answers tagged

9

As written, the question is a bit trivial: if NP = NP-complete, then since P $\subseteq$ NP we get P=NP since every problem in P would be NP-complete. I suspect what's meant, though, is the following: Suppose there are no NP-intermediate problems; that is, that every problem in NP is either in P or is NP-complete. What does that tell us about P vs. NP? ...


5

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3]...


3

Since $P \subseteq NP$, if the statement is false, it cannot become true by changing $P$ to $NP$. What your teacher is doing here is trying to illustrate a very common fallacy amongst beginning CS-learners. He is giving one potential way to solve a problem, and he notes that this way needs more resources than we want to make available (sometimes it is ...


3

Very simple: We can sort an array without checking every possible permutation. (Many times we don’t check any permutation of the array, we just re-arrange the order of items so we can guarantee the array is sorted, without ever checking it. )


2

You are confusing NP and NP-hard in a couple places. For example, let $A$ be the problem of deciding ATL*, which is 2EXPTIME-complete. $A$ is NP-hard and polynomial-time many-one reduces to its complement, but is neither in NP nor in co-NP by the time hierarchy theorem. Recall that an NP-complete problem is one that is in NP and is NP-hard. For every NP-...


Only top voted, non community-wiki answers of a minimum length are eligible