72

there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems. This statement is wrong. There are many NP problems which are easy to solve. "NP" simply means "easy to verify". It does not mean hard to solve. What you are probably thinking of is NP-complete problems which is a ...


27

Generally speaking, the following is true for any algorithm: Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time. Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain ...


15

The monotone version of X3SAT that your proof is based on has the nice property that setting a literal false in one clause will never cause the negation of that literal to be true in another, which means you can say The only way a conflict can occur is when all literals in a clause are set to false. and it will be true because forcing two literals false ...


11

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case. If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard. For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this ...


10

It is true that many algorithms that have quadratic running time are not the state of the art for their problems today. Among which are quadratic sorting algorithms for example bubble-sort, select-sort and insertion-sort, which are overcome by merge-sort and heap-sort. On a side note, quick-sort, the standard sorting algorithm in different areas, has a worst ...


9

Don't trust plots. By Stirling's approximation (and dropping the ceilings to avoid notational overload), $$\begin{align*} (\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\ &= \sqrt{2\pi \log n}\, e^{(\log\log n - 1)\log n}\\ &= \sqrt{2\pi \log n}\, n^{\log\log n - 1}\,, \end{align*}$$ which grows faster than any ...


9

Yes. Here's a sketch of a direct proof. If a problem is in $\mathrm{NP}$, there is a nondeterministic Turing machine $M$ that decides it, and there's a polynomial $p$ such that none of $M$'s computation paths on inputs of length $n$ take more than $p(n)$ steps. That means that a single path can't use more than $p(n)$ tape cells, so we can ...


9

Because then their experiment would have been a complete failure. As I wrote in an answer on a sister site (which was somewhat poorly received there, but I think your question validates what I was saying about how a general audience interprets it): [the hyping of the result] plays on a discrepancy between what they mean by quantum supremacy (QS) and what ...


9

Yes, and this holds even for structured graphs. Indeed, every planar graph is 5-colorable (in fact even 4-colorable by the Four color theorem), but it is NP-complete to decide if a planar graph can be colored in 3 colors.


9

The existence of such an algorithm would imply co-NP is included in NP which is unlikely Checking that a formula is satisfiable: NP, generate proof by providing a solution Checking that a formula is unsafisfiable: co-NP, generating proof can be harder, in classical proof systems the shortest proof of unsatisfiability of an arbitrary formula can be ...


8

There is a logical interpretation of the various levels of the polynomial hierarchy, which extends the witness characterization of $\mathsf{NP}$ and $\mathsf{coNP}$. A language $L$ is in $\Sigma_k^P$ if there is a polytime predicate $f$ and a polynomial $\ell$ such that $$ x \in L \Leftrightarrow \exists |y_1| \le \ell(|x|) \; \forall |y_2| \le \ell(|x|) \; ...


8

The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ ...


8

Any upwards-closed non-empty class $\mathfrak{L}$ of languages has the cardinality of the continuum, with very few limitations on what kind of reasonable reducibility we are looking at. The reason is if $A \in \mathfrak{L}$ and $B$ is an arbitrary language, then the language $A + B = \{0w \mid w \in A\} \cup \{1w \mid w \in B\}$ satisfies that $A \leq A + B$,...


8

Your algorithm is known as greedy coloring. Wikipedia gives an example of a bipartite graph, the crown graph, where the greedy coloring can produce a coloring using $n/2$ colors (for the worst ordering). For random $G(n,1/2)$ graphs, the greedy coloring typically produces a coloring using double the optimal number of colors.


7

First, let us see what the halting proof attempts to prove: There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $y$. We call the function which $H$ is supposed to compute the halting predicate. The program you are suggesting, which consists of simulating a run of ...


7

You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the statement $$\lnot \exists x . \phi(x)$$ we do as follows: Assume that there is $x$ such that $\phi(x)$. We assume this even though perhaps we have no idea how to ...


7

Quantum computing is not a piece of magic, and there seems to be a widespread misconception about the power of quantum computers. I am by no means an expert in this field, but as far as I know QC is very suitable for computational problems that employ some kind of cyclic structure. This happens to be true for problems like the integer factoring problem and ...


7

You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G_1,G_2)$ which are isomorphic. Two graphs $G_1 = (V_1,E_1),G_2 = (V_2,E_2)$ are isomorphic if there exists a bijection $f\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(f(x),f(y)) \in E_2$. You take it from here.


7

You can easily write a polynomial-time algorithm to decide $L_1$ (just count the zeros and check you see the same number of ones), so the language is in $\mathrm{P}$. Most non-regular languages are not in $\mathrm{P}$ because there are uncountably many languages in total, but only countably many languages in $\mathrm{P}$. The halting problem ...


7

Nondeterministic machines are only allowed to behave nondeterministically in a limited way: very briefly, "Accept iff some branch has [property]" is permitted but "Accept iff no branch has [property]" is not. Unlike with deterministic machines, there's a fundamental element of asymmetry here. Your $N'$ is not, in fact, a nondeterministic Turing machine. ...


6

7 is the least number of questions that you can ask to guarantee to find the treasure. the idea of binary search Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search. the binary search on ...


6

The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(\sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(\sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/...


6

Let $V(i, W)$ be the maximum sum of the values of the items among the first $i$ items so that the sum of the weights is less than or equal to $W$, then we have $$V(i, W)=\max\{V(i-1, W), v_i+V(i-1,W-w_i)\}$$ where $v_i$ and $w_i$ are respectively the value and the weight of the $i$th item. Suppose there are $n$ items and the capacity limit is $W_\max$, ...


6

The problem you have stated probably contains an error: Given a set $N$ with $n+2$ numbers,‚Äč such that the first $n$ numbers are positive and rational with sum $1$, the $(n+1)$st number is $\sqrt{2}$, and the $(n+2)$nd number is $2 - \sqrt{2}$, determine whether there is a subset of $N$ such that the sum of the subset is $3/2$. The answer is that there ...


6

Turing machines are a nice model with several advantages, mostly their simplicity, but they are not the first choice when analyzing algorithms. Algorithms are typically implicitly analyzed on the RAM machine model, and in some cases, on the BSS model. Here are some comments on the computational complexity of counting in various models: Single-tape Turing ...


5

P, NP, NP-complete and NP-hard are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties: Solvable in polynomial time: Defines decision problems that can be solved by a deterministic Turing machine (DTM) using a polynomial amount of computation time, i.e., its running ...


5

Because, if you only use $f(n)$ tape cells, there are at most $|\Sigma|^{f(n)}$ possible strings you can have written on the tape, at most $f(n)$ different places the tape head could be, and at most $|Q|$ different states the Turing machine could be in. That means there are at most $|Q|\,f(n)\,|\Sigma|^{f(n)}$ different configurations for the machine. If ...


5

In order to break a one-way function, it suffices to be able to find a single preimage. Given $x$, $f(2x) = x$, so finding a preimage of an arbitrary input is easy. Hence it's not a one-way function at all.


5

It isn't meaningful to say that a single specific question is in NP or any other complexity class. In order to classify things as being in P, or NP, or co-NP, etc. they need to be sets of problems with some parameter. So for example, the problem "Is the positive integer n prime" is a question where we can discuss this sort of thing. In a certain overly ...


5

As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know. As you can see there, the complete statement of Baker, Gill, Solovay is: There exist oracles $A, B$ s.t. $P^A = NP^A$ and $P^B \neq NP^B$ The second oracle cannot be considered a counterexample for $P = NP$ because you cannot "...


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