New answers tagged complexity-theory
0
There is a one-to-one correspondence between NFAs and right regular grammars without productions of the form $A \to a$.
Given a right regular grammar with productions of the form $A \to aB$ and $A \to \epsilon$ and starting symbol $S$, create an NFA in which:
The states are all nonterminals.
The initial state is $S$.
A state $A$ is final if there is a ...
2
We can understand it as set $\{2^{f(n)}: f \in O(n)\}$.
For example any $n^k,k>0$, will be in $2^{O(n)}$: $n^k=2^{k\log_2 n}$ and we have $\log_2 n \in O(n)$.
Note: I especially not write $k \cdot \log_2 n \in O(n)$, because multiplication on positive constant has no influence.
3
Reduction Rule 1. Let $V$ be the set of vertices which are isolated. Convert the instance from $I = (G,k,d)$ to $I^{'} = (G -V, k,d)$. If $I^{'}$ is a yes instance, then so is $I$, because adding back the isolated vertices do not add on to the degree of other vertices. And isolated vertices have already have degree 0 ($\le d$ as $d \ge 0$). And if $I$ is a ...
1
You can't create a uniformly random number in $[0,1]$ in finite time, because that would require infinite precision.
Probably that's not what you want. Probably you want to generate a random float in the range $[0,1]$. Then we have to ask what assumptions you are willing to make about your pseudorandom number generator. For many of them it is probably ...
0
Regardless of whether or not P=NP unlike what the other answers seems to claim this problem is way too much over hyped.
Why it doesn't matter if P = NP (at least in the practical sense)
People think the P,NP problem is an important question because they think that if someone would solve an NP complete problem in polynomial time it would change the world or ...
0
for the first code segment, input size is 2n. a has n elements, so does b.
for the second code segment, input size is 2n. a has n elements, so does b.
for the third segment, input size is n+1. a has n elements, and there is another value n.
for the fourth code segment, input size is 2.
0
I think that Time Hierarchy Theorem can be an argument in favor of $P = NP$: there exist problems which can't be solved in time $O(n^{100})$, but can be solved in time $O(n^{101})$. I didn't see arguments why SAT can't be one of such problems.
The common argument is that there are tons of NP-complete problems, and for none of them we have a polynomial-time ...
3
Without taking any stance, here are 8 arguments I made to help you believe that P=NP is possible:
1. Primes is in P
AKS primality test has O(log(n)^6) complexity. Here, the complexity of solving does not increase exponentially with the size of the input. However, multiplication is (either naïvely or correctly?) assumed to be a one-way function.
2. Problems ...
0
The string $u$ is the certificate for $x$ with respect to $L$ and $M$, while the string $y \circ z$ is the certificate for $\phi_x$ with respect to $SAT$ and a verifier TM for SAT. $M$ is an oblivious deterministic TM with two tapes - an input tape and a work/output tape. Although I did not find this clearly stated anywhere, it seems reasonable to assume ...
1
No, I'm not aware of any research in this direction, probably because it is not very promising. This does not seem to me like a promising approach to solve NP-hard problems efficiently, or other hard problems efficiently. The hard part would be how you would find that decomposition; I don't know of any reason to think that's particularly easier than ...
3
$X$ doesn't exist (unless $P = NP$ in general) because your description is self-contradictory. You claim it is NP-hard, yet its input domain can be split in a finite number of disjoint poly-time solvable problems. This makes it $P$.
The idea of executing these algorithms in parallel adds nothing. Even on a single machine you can run N programs '...
1
Let $f\colon \{0,1\}^n \to \mathit{GF}(q)$. Then
$$
f(x) = \sum_{y \in \{0,1\}^n} f(y) \prod_{i\colon y_i=0} (1-x_i) \prod_{i\colon y_i=1} x_i.
$$
This shows that any function from $\{0,1\}^n$ to $\mathit{GF}(q)$ can be represented as a multilinear polynomial.
Now let us show that the representation is unique. This follows from dimension considerations (the ...
1
Let $AND:\{0,1\}^n\mapsto\{0,1\}$ be a polynomial in $GF(q), q\geq 2$.
Notice that the polynomial can't have a constant term (the constant term is zero), because
$AND(0,...,0) = 0$.
Meaning we can write the polynomial as:
$$AND(x_1,...,x_n) = \sum_{S\subseteq[1,n], S\neq \emptyset}a_S\prod_{j\in S}x_j$$
We now claim that every non-zero summand in $AND$ ...
4
Given your contraints, I think Counting sort or Radix sort will do the job.
https://en.wikipedia.org/wiki/Counting_sort
https://en.wikipedia.org/wiki/Radix_sort
1
Papadimitriou is being extremely sloppy here. Let us consider part (b) first. What does Papadimitriou mean by "ink"? Suppose that he really means what he wrote: the number of times during computation that a symbol is overwritten by a different symbol. Consider a Turing machine which repeatedly goes right one step, then left one step, in an infinite ...
0
Beginner myself, but here is my attempt(in Layman terms).
1 ) there is no $ϵ>0$ such that a problem can be solved in $O(n^{2−ϵ})$ time
This means that the problem cannot have a worst solution with an order of growth of at most $cn^k$ where $k\in [0,2)$ and $c$ is some +ve constant.
3 ) a problem requires time $Ω(n^2)$
This means that the best solutions ...
1
Let $L'$ be an arbitrary language, and consider
$$
L = \{ \Sigma^{|x|} x : x \in L' \}.
$$
Then $L$ has roughly the same complexity as $L'$, but it has communication complexity $1$.
2
If Your first statement
there is no $\varepsilon>0$ such that a problem can be solved in $O(n^{2−\varepsilon})$ time
we understand as negation of
$\exists\varepsilon>0,f \in O(n^{2−\varepsilon})$
Then it will be $\forall\varepsilon>0,f \notin O(n^{2−\varepsilon})$ which is set
$$A=\left\lbrace f:\forall\varepsilon>0, \forall C>0,\forall N\...
3
No. Let $L_0$ be a context-free language, say the language of matched parentheses, $L_1 = \Sigma^* \setminus L_0$, and
$$L = \{ij \mid b \in \{0,1\}, i \in L_b, j \in L_b, |i|=|j|\}.$$
Then $L$ is not regular, but it has communication complexity $O(1)$.
5
It is conjectured that 3SUM cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon > 0$; equivalently, it requires time $n^{2-o(1)}$. This is not the same as the stronger conjecture that 3SUM requires time $\Omega(n^2)$. Indeed, the latter conjecture (which was the original form of the 3SUM conjecture) is false: Grønlund and Pettie came up with an ...
1
Let's say the NP complete problem A can be solved in O(f(n)), where n is the problem size. And B can be solved in O(g(n)), where g is much larger than f. If we reduce an instance of B to an instance of A, the problem size is very unlikely to stay unchanged. Lets say the problem size is changed from n to h(n), and the time used for the reduction is negligible....
4
The state of affairs as of 2013 is described in Mertens and Moore, The Complexity of the Ferminonants and Immanants of Constant Width. Let $\lambda$ be the partition corresponding to $\chi$.
Immanants are easy if the leftmost column of $\lambda$ contains $n - O(1)$ boxes (Barvinok; Bürgisser).
Immanants are hard if $\lambda_i - \lambda_{i+1} = \Omega(n^\...
1
Here is a way to see that there could be arbitrarily large differences between the optimal time complexities of different NP-complete problems.
Suppose P = NP. Then any problem in P with at least one accepting input and at least one rejecting input is NP-complete. By the time hierarchy theorem, there are problems that take $\Theta(n)$, $\Theta(n^2)$, $\Theta(...
4
A polynomial-time reduction only needs to preserve the size of the problem up to a polynomial upper bound (which is implied by the time constraint).
As an example, suppose you have two NP-complete problems and $A \le_p B$, the reduction blows up the instance size from $n$ to $n^2$, and $B$ admits an algorithm with running time $ 2^\sqrt{n}$. This only ...
0
The problem is in P.
You can solve the decision problem in $O(n^2)$ time, where $n$ is the number of vertices (i.e., linear time in the size of the input). Delete all edge whose weight is above the bottleneck threshold. Form the strongly connected components of the resulting graph, and examine its metagraph. The original decision problem has a bottleneck ...
0
Think first that 'will my program halt?'. If you are sure that yes, your TM will definitely HALT then go for any searching algorithm, no problems at all. But, if are not sure about the HALTING issue, then? A TM is an idealized computer because the amounts of time and tape memory that it is allowed to use are unbounded. When it falls in ‘loops’ it may run for ...
3
If $f = \prod_{i=1}^d x_i$ is a single monomial then
$$
\Pr[f=0] = 1 - \left(1 - \frac{1}{|\mathbb{F}|}\right)^d \geq \frac{d}{|\mathbb{F}|} - \frac{d^2}{2|\mathbb{F}|^2}.
$$
(The second bound is Bonferroni's inequality.)
This shows that Schwartz–Zippel is essentially tight when $d$ is small compared to $\mathbb{F}$.
The bound $1-(1-1/|\mathbb{F}|)^d$ is ...
5
The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks.
Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition problem to this problem.
[1]: Buss, Sam, and Michael Soltys. "Unshuffling a square is NP-hard." Journal of Computer and System Sciences 80.4 (2014): 766-...
0
You're probably not going to get a theoretical answer, because analyzing exactly what set of functions can be computed by a particular neural network is messy. Or, at least, you probably won't get a tight analysis. There are theorems showing that neural networks are universal approximators, meaning that given sufficient capacity it is possible to express ...
0
It is not entirely clear to me where the warehouses are allowed to be placed. I will assume here that a warehouse can be placed in any city given by the input1.
instead of minimizing the distance [$t$], I want to fix it and minimizing the number of warehouses. is this problem NP-Complete also?
Observe that we may assume the maximum allowed distance $t=1$, ...
1
Hint: Take a SAT instance $C$ with $k$ clauses and introduce $3k$ new variables $\top^i_1, \top^i_2, \top^i_3$ for $i \leq k$ and construct $k$ new clauses $c^\top_i = \{ \top^i_1,\top^i_1,\top^i_3 \}$. Let $C' = C \cup \bigcup_{i=1}^k c^\top_i$ be the input to 3SAT-WITH-MAJORITY.
1
To self-study from Computational Complexity: A Modern Approach, the prerequisites are:
A few courses in algorithms* (you should be comfortable reading and writing pseudocode, using Big-$\mathcal O$ notation, and using abstract data structures like lists, sets and hashmaps)
A course in discrete math
A course which treats Finite State Machines and formal ...
Top 50 recent answers are included
