New answers tagged complexity-theory
0
To give you an idea of the “why”: A yes/no problem is an NP if you can prove the answer is “yes” by making an incredibly lucky guess, plus some moderate amount of work.
For example: Can I make a tour connecting the capitals of the 48 main states of the USA in at most 10,000 miles? If the answer is “yes” then I make a lucky guess in which order to visit the ...
0
The algorithm to compute $G'$ is really easy: just return $G$.
Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.
To prove this you can show that we must simultaneously have $E \subseteq E'$ and $E' \subseteq E$.
Proof that $E \subseteq E'$: Suppose ...
5
Your analysis of the time complexity is wrong. Specifically this statement:
In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at.
In fact you can have up to $\binom{n}{s}$ $s$-cliques.
You approach is essentially enumerating all cliques of size up to $k-1$. So you cannot hope to have a running time ...
2
Big O notation is oblivious to this difference. This is one of its downsides.
One reason we use big O notation in the first place is that the exact running time depends on the system used to run the algorithms. It is meaningless to say that a given algorithm takes X instructions, since X depends on the CPU, the compiler, and so on. However, in some cases we ...
1
Queue automata are Turing-complete, so they can simulate any machine, including a two-counter machine.
2
A decision tree is a special kind of "program" which computes a function, usual from $\{0,1\}^n$ to $\{0,1\}$. Let's take an example from Wikipedia:
A decision tree is a binary tree. Internal nodes are labeled by functions from a set $\mathcal{F}$ (more on this, later). Leaves are labeled by elements from $\{0,1\}$. Each internal node has one ...
1
I understood the question as "select a subset of size $2k$ from $F$ such that (there exists coloring for $F$ $\iff$ there exists coloring for the subset)".
As you've said, you can remove all singleton and empty sets. The remaining sets have at least $2$ elements. You can show that any $2k$ such sets suffice.
Select $2k$ arbitrary sets with at least ...
0
No, because $A$ isn't necessarily $NP$-complete and $B$ isn't necessarily $coNP$-complete. You'd need both to be true to force the implication $NP = coNP$ by $X$ being a member of both problem classes. In fact $A$ and $B$ could both be in $NP$ and $coNP$. E.g. $A$ and $B$ could both be in $P$. $NP \cap coNP$ is not the empty set.
2
This problem is indeed $NP-complete$ as you have suspected. To see this, we will show a reduction from $SubsetSum$.
The reduction
Let $A,s$ be an instance of $SubsetSum$, where $|A|=n$. We will define $L$ as all the numbers in $A$, in addition to another $n$ zeros. For example, if $A= 4, 5, 8$ then $L=4,5,8,0,0,0$.
Now, we define $M$ to be with $2n$ values, ...
1
Im assuming the OP meant the question is $(\forall M. M \text{ is nondeterministic polynomial TM }, L(\overline{M})\in P) \iff P=NP$.
Look at Steven's answer for the solution regarding the other interpretation of this question.
This proof assumes $\overline M$ is a TM that accepts $(w, x)$ where $w$ is a witness for $x $, iff $M$ rejected $(w,x)$. This does ...
1
As usual with zero-knowledge proofs, this is an interactive proof. A prover is trying to prove that he has a satisfying assignment to some 3-SAT formula without giving away the assignment. A verifier is trying to build up enough statistical evidence to believe the prover. The proof proceeds as a series of rounds and continues until the verifier is ...
0
Problem: Is a = b?
Reduction to bin packing: Assume you have bins of size (a+b)/2. Can one item of size a and one item of size b be packed into 2 bins?
We just reduced a very, very simple problem to an NP-complete problem.
1
Let's imagine a Non Deterministic Turing Machine $M$ that decide $SAT$. If we tune this machine a bit, and add a transition on the initial state, for every letter read, that reject the entry. Let $M'$ be the new NTM. Then, $L(M') = L(M)$, since $u\in L(M) \Leftrightarrow \exists$ at least one computational path in $M$ to an accepting state (and the same ...
2
This was proved NP-complete in "Optimal Packing and Covering in the Plane are NP-complete" (Fowler, Paterson and Tanimoto, Information Processing Letters 1981). I found a freely available version of the paper here. They give a neat reduction from 3SAT -- I'll summarise this below, but the paper is short and easy-to-read with several diagrams, and I ...
1
Suppose that all problems in the world could be ranked in terms of difficulty, where higher numbers correspond to more difficult problems.
If $B$ is NP-hard then its ranking is large, $r(B) \geq M$.
If $A$ reduces to $B$ then $A$ is not harder than $B$, that is, $r(A) \leq r(B)$.
Given $r(B) \geq M$ and $r(A) \leq r(B)$, can you conclude any lower bound on $...
0
The value of $\lceil\log_2(n)\rceil$ is more or less equal to the number of bits in the binary representation of $n$ (except if $n$ is a power of 2).
You can then imagine a Turing Machine with an input tape (on which is written the number), a work tape and an output tape. First, you need to convert your unary number on the input tape, into binary on the work ...
0
Your grammar is not correct.
To see this notice that no sentence generated by your grammar can have more than two "c"s.
Indeed, the only productions that generate one or more occurrences of "c" are $S \to abc$ and $XZ \to Ybcc$.
Clearly, if $S \to abc$ is used, the resulting sentence has exactly one "c" (no production has $S$ on ...
0
Edit: my answer applies to the first post before modification.
It seems to me that your grammar is not correct. For exemple, if you use the first rule for $S$ then the second rule for $S$, you get $aabcXY$ and no rule can be applied from there.
Inspired by what you proposed, it seems that the following rules are right :
$$S \rightarrow aSXY | abc$$ $$cX \...
2
B being NP-hard does not say anything about A. The problem says that there is a way to reduce A to B in polynomial time.
But on the other hand, it is also not given that A getting reduced to B is the only pathway for solving A. So, there can be other ways of solving A in polynomial time.
Hence, the implication that A is NP-hard is false.
1
Here is an example. Consider the problem of vertex cover. An instance of vertex cover consists of a graph $G$ and an integer $k$. This is the domain $D$. You can easily come up with a one-to-one encoding $e\colon D \to \Sigma^*$ such that (i) you can recognize whether a string is in the range of $e$ in polynomial time, (ii) given such a string, you can ...
2
Skew arithmetic circuits are usually defined a bit differently: in every multiplication gate, one of the inputs of the gate is a constant or an input of the circuit (we assume that multiplication gates are binary).
This is very similar to your definition, if linear is interpreted as syntactically linear. That is, one of the inputs of any multiplication gate ...
1
A "trapdoor" function is a function which is hard to compute, but will become very easy (or a lot easier) to compute if you have some specific knowledge.
The classical example is solving y = x^3 (modulo n) where n is the product of two very large primes; it is the basis of RSA encryption and practically impossible to solve given x and n, unless you ...
2
If the greediness here means moving on the input based on a specified score, and computation of the input item's score is polynomial, the answer is yes. It is correct. Because moving on the input with $n$ items is linear, and if the scoring computation for each item will be polynomial, as sorting them will be polynomial as well; finally, we can solve the ...
1
Probably you can get your answer from here: Reducing independent set to triangle-free subgraph
Basically in order to prove that $TFS$ is NP-complete you can just check the first proof in the link's answer. Given a graph $G$ with an independent set $k$, there exists a $G'$ with a $TFS$ of size $|V|+k+1$.
5
What you're misunderstanding is how "problem" is used in computer science. "Problem" does not refer to finding the correct output for a particular input, but writing an algorithm that returns the correct output for all inputs. For instance, is there an algorithm that sorts a list in linear time? You could write a program that simply goes ...
0
If $A \leq_P B$ then since $P \subseteq P/\mathit{poly}$, also $A \leq_{P/\mathit{poly}} B$. This means that there is a function $f \in P/\mathit{poly}$ such that $x \in A \leftrightarrow f(x) \in B$. Since $f \in P/\mathit{poly}$, for every $n$ there is a polynomial size circuit $C$ that computes $f(x)$ for $x$ of length $n$. The circuit needs to have some ...
1
Here is a zero-knowledge protocol for E3SAT, the variant of SAT in which each clause contains exactly three literals.
Consider an instance of E3SAT, consisting of variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.
Prover chooses a color in $\{1,2,3,4\}$ for each of the following:
Variable literals $V(x_i), V(\lnot x_i)$ ($2n$ colors in total).
...
1
So, Captain Kirk tells the android that Harry Mudd is a liar. Everything he says is a lie. The android accepts this premise, whereupon Harry Mudd says, "I am lying." The android expresses confusion that Mudd cannot be lying b/c that would be true and that cannot be true b/c he is a liar. Smoke comes out of his ears and Kirk saves the day! This is ...
2
I find postings above saying a computer can decide the truth or falsity of some statements but not of some others.
I find that a somewhat misleading way of putting it. For statements in first-order logic, a computer can search for a proof and if one exists it will find it. But if the program has been running for a trillion years and hasn't yet found a proof, ...
3
The computability-based generalized incompleteness theorem with its proof would shed more light on your question. In particular, Yuval's answer states but does not prove that the set of true arithmetical sentences (true according to the standard model $(ℕ,0,1,+,·)$ of PA) is undecidable. The linked post shows via reduction to the halting problem that the set ...
2
Other people have covered explaining the actual meaning of the theory this paragraph referenced. I will instead address how the quoted paragraph was intended to be interpreted, such that it does in fact correctly describe the theory.
During the first half of the twentieth century, mathematicians such as Kurt Godel, Alan Turing, and Alonzo Church discovered ...
0
Worse-case complexity gives an upper bound on the complexity of an algorithm in terms of some parameters. Often the parameter is the length of the input, either in bits or in words, but sometimes several parameters are pertinent. The standard example is graph algorithms, where complexity is often expressed in terms of both the number of vertices and the ...
0
You can write a computer program that will prove / disprove some mathematical theorems. There are some problems that can be solved very easily but need an enormous number of steps to solve; computers can handle them easier than humans. For example the statement “1526753673279839 is a prime” is no big deal for a computer.
But there are two problems. One is ...
3
We give a Turing reduction from the $\mathrm{SubsetSum}$ problem.
Suppose we are given a $\mathrm{SubsetSum}$ instance $(A, k)$ where w.l.o.g. $A$ only contains positive integers, i.e. we want to find a set $X \subseteq A$ such that $\sum_{x \in X} x = k$ and define the set $A' = A \cup \{- k\}$.
We want to show that $f(A') = 0$ if and only if $(A, k) \in \...
0
I suggest following property: if for functions $g,f \gt 0$ we have $f \sim kg$, for some constant $k\gt 0$ i.e. $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=k$ and both, $g$ and $f$, have not zero as limit point, then $O(f)=O(g)$.
Proof:
Let's consider $\phi \in O(f)$, then we have $\phi \leqslant C f \leqslant C (k+\varepsilon)g$ for appropriate $C, \...
0
If we analyze a Time Complexity dependent also on the values of a given input, then as you say a more defined notation would be O(max(n)).
Though, saying O(max(n) + n) in O notation means O(max(n))
So it will still be accurate, since in both outcomes the Complexity is linear in the given input.
7
The statement is overly broad, as well as being overly complimentary to people. Computers can’t solve all problems but neither can people. Not sure why the extra drama was added.
What that is referring to is basically an aspect of the Halting Problem. A Turing machine can determine the answer to some questions but is unable to do so for others. They even ...
5
A simple example of undecidable mathematical statements are whether multivariate integer polynomials have natural roots.
This means that we an expression $E(n_0,\ldots,n_k)$ built from natural number constants, natural number variables $n_0,\ldots,n_k$, addition, substraction and multiplication. We then want to know whether a solution for $E(n_0,\ldots,n_k) =...
2
Shameless self-promotion: Under standard complexity assumptions, A full complexity dichotomy for immanant families shows that immanant families (satisfying minimal computability and density requirements) are polynomial-time computable iff the involved partitions have only finitely many boxes outside of the first column.
2
Suppose that the longest word in the language has length $m$. The Turing machine reads the first $m+1$ symbols on the input tape. Based on that, it can decide whether the input belongs to the language or not. This Turing machine runs in constant time.
11
It isn't a matter of implementation. It's a matter of different approaches to parsing that unfortunately have similar names.
NFAs and DFAs (finite-state machines) can only recognize regular languages. Regular expressions are a way of specifying regular languages, and they can be compiled into efficient NFAs or DFAs that recognize the language. This is all ...
29
On top of what everyone else has said, it may be worth talking about where some of the boundaries of decidability and undecidability are.
For natural numbers:
The first-order theory of natural numbers with only addition (Presburger arithmetic) is decidable.
The first-order theory of natural numbers with only multiplication (Skolem arithmetic) is decidable.
...
1
Look at the time hierarchy theorem for an explanation. In particular, we know (using this theorem) that $P\subsetneq E\subsetneq EXP\subsetneq R$, and we could have added a lot more complexity classes in between them.
12
The key is quantifiers, both in the theorem, and in the "mathematical statements."
First, the theorem says that "there is no algorithm that can take in an arbitrary mathematical statement and prove if it is true or false." This does not mean that, for every mathematical statement, a computer can't determine if it's true or false. It just ...
72
The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not.
The standard choice for the class $\mathcal{C}$ is statements about ...
7
Cox's post is still relevant and up-to-date. The key quote is this one:
Most of the time, in fact, regular expression matching in Perl is fast enough. As the graph shows, though, it is possible to write so-called “pathological” regular expressions that Perl matches very very slowly. In contrast, there are no regular expressions that are pathological for ...
0
Given $a,b,c\in\mathbb Z$ the quadratic program
$$\exists x,y\in\mathbb Z$$
$$ax^2+by-c=0$$
is known to be $\mathsf{NP}$-complete by https://www.sciencedirect.com/science/article/pii/0022000078900442. If you had no non-linear constraints but a non-linear objective it is called a linear program having a non-linear objective (for example a convex objective). $\...
0
You can modify the CYK parsing algorithm so that it counts the number of parse trees for each word.
Given a word $w = w_1 \ldots w_n$, for each $1 \leq i \leq j \leq n$ and non-terminal $A$, we will count the number of parse trees rooted at $A$ and generating $w_i \ldots w_j$. If $i = j$ then this number is either zero or one, depending on whether $A \to w_i$...
3
They are not precisely the same language. For instance, $\overline{SAT}$ has words that are not even formulas. $UNSAT$ on the other hand, has only formulas that are not satisfiable.
In terms of complexity measures - the two languages are equivalent, since we can check in polynomial time whether a given input word is a formula or not and therefore we have a ...
1
It's unclear what $n$ is in your question. If your matrix has dimensions $n \times n$ and your model of computation allows you to perform
basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $O(n)$ time.
Top 50 recent answers are included
