New answers tagged complexity-theory
0
votes
Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)
Pivot is unique in the whole array, therefore every sub array containing pivot contains a unique item. Subarrays not containing pivot are the subarrays of the array from start to pivot-1 and the ...
- 28.3k
0
votes
Accepted
Complexity of satisfiability for relational logic on the booleans
In NP I could guess the disjunctive normal form of the formulas, that would look like
$\bigwedge_i R_i(x_1^i, \ldots, x_{n(i)}^i) \land \bigwedge_j \lnot R_j(x_1^j, \ldots, x_{m(j)}^j)$
The question ...
- 2,184
1
vote
Accepted
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
I think there must be some confusion in the problem setting. Given an input of $n$ bits chosen uniformly at random, there is no algorithm to compress it to something whose length is on average ...
D.W.♦
- 156k
0
votes
Variant of Bounded Subset Product
The problem can be solved in polynomial time, using dynamic programming.
Let $A[k,s]$ be true if there exists a solution to your problem where $f_1 \cdots f_k = s$, or false otherwise. You can fill ...
D.W.♦
- 156k
1
vote
Complexity of satisfiability for relational logic on the booleans
Nothing much changes. Every relation $R(x_1,\dots,x_n)$ is equivalent to $\exists t_1,\dots,t_m . \varphi(x_1,\dots,x_n,t_1,\dots,t_m)$ for some fresh variables $t_1,\dots,t_m$ (see the Tseitin ...
D.W.♦
- 156k
2
votes
Can you compute a majority function of n-bits using an O(n) size circuit?
Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion.
At the $i$-th level of the tree you're dealing with numbers with at most $i+1$ bits.
Hence the number of gates ...
- 28.2k
1
vote
If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine
The idea is to use the self-reducibility of SAT to construct a search-to-decision reduction.
Suppose that we have in our disposal an oracle that solves SAT, and we wish to use it to find a satisfying ...
- 275k
0
votes
Accepted
$NL$ Leaf languages and $PSPACE$
You are omitting some very important details. In the exercise, the Turing machine $N$ is required to halt on all its possible computation paths using exactly $p(n)$ steps, where $n$ is the size of the ...
- 28.2k
1
vote
Accepted
A machine with multiple oracles
The definition of an oracular complexity class is key to answering this question, it is often defined as:
$$
\mathsf{C^{A}=\bigcup_{L_A\in A}C^{L_A}}
$$
But how do we define two oracles? Well the ...
- 26
1
vote
Communication complexity of Dyck language
TL;DR: $n \le C(f) \le n+1$.
We can easily prove that $C(f) \ge n$. Consider the set of $x \in \{(,[\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need ...
D.W.♦
- 156k
0
votes
Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes
You can't do it in polynomial time (unless P = NP), since it is as hard as the Hamiltonian path problem (consider the special case where you must visit all nodes). One standard approach if you have ...
D.W.♦
- 156k
0
votes
Hardness of approximation for Disjoint Group Steiner Tree
As noted in the second paragraph of section 18.2 of these lecture notes, https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec18.pdf, one can actually assume that the groups are ...
- 471
0
votes
Prove NP-completeness of deciding satisfiability of monotone boolean formula
IMO, it is intuitive to reduce Vertex-Cover to the problem that you are describing (which will show that the problem you are describing is at least as hard as Vertex-Cover). At the core of the problem ...
0
votes
Is there a known polynomial time complexity problem with bad constants?
Another simple one, that turned up in another question. Given a finite set S, sorting any array of elements of S can be sorted in linear time using counting sort (or without any additional storage: By ...
- 28.3k
2
votes
Accepted
What is the complexity of minimising a convex quadratic function over the integers?
The closest lattice vector problem is NP-hard in the $L_2$ norm. See NP completeness of closest vector problem for a reference to the proof.
D.W.♦
- 156k
0
votes
NP completeness of closest vector problem
There is a mismatch in terminology in your question. The problem you specify is known as the shortest vector problem (SVP). You called it the closest vector problem (CVP), but the CVP is something ...
D.W.♦
- 156k
0
votes
Reducing euclidean TSP of smaller size to euclidean TSP of bigger size
Here's an idea that doesn't work: Assume K = N-1. Take any node X and create another node X' at a distance epsilon from X, and calculate all the distances to X', then solve the N problem. If that ...
- 28.3k
0
votes
Parallel Algorithm Analysis: Loops
The work $W(n)$ is the total number of nodes in your computation
graph and the span $D(n)$ is the number of nodes on the longest path
of that graph. $T_P(n)$ is the runtime of the algorithm
using $P$ ...
- 1,151
13
votes
Is there a known polynomial time complexity problem with bad constants?
A simple one: Given n chess positions, find an optimal move for each position.
The game of chess is finite, so finding an optimal move for any position is O(1), and for n positions it is O(n). With a ...
- 28.3k
7
votes
Is there a known polynomial time complexity problem with bad constants?
To add another perspective on this: there is a class of problems known as fixed parameter tractable (FPT) which has been studied extensively. In this area of research, one studies problems that, given ...
- 6,958
0
votes
True or false? Any finite problem is in P
If by finite problem, you mean a problem with a finite domain, then yes. Such problems are not only in P, but can be done in constant time since you can build a mapping between every possible input ...
26
votes
Accepted
Is there a known polynomial time complexity problem with bad constants?
Such algorithms are called Galactic Algorithms.
- 5,797
0
votes
( Soft question ) P vs NP - is such a situation possible?
Consider what happens if I find a polynomial time solution for an NP complete problem. Say a solution taking $n^{100}$ nanoseconds on my computer.
For n = 2 that’s $2^{100} \approx 10^{30}$ ...
- 28.3k
1
vote
Dinitz’ algorithm in simple unit-capacity networks
I have no clue about how the values in the other two lemmas are brought up.
The how is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized?
The answer is $\sqrt n$, ...
- 15.5k
2
votes
Complexity of simulations in simulations
You can build a universal Turing machine with only 7 states, or only 15 states if you require that the tape store binary symbols. See https://en.wikipedia.org/wiki/Universal_Turing_machine#...
D.W.♦
- 156k
0
votes
( Soft question ) P vs NP - is such a situation possible?
Yes of course it is possible. Everything is possible. Such situations have been rare in mathematics, so I would not bet on it, but we have no way to rule out such a possibility. We do know that ...
D.W.♦
- 156k
1
vote
Time complexity of search algorithms?
Let $A$ be a comparison-based search algorithm that takes a collection $C$ of $n$ elements and an element $x$ as input and outputs the position of $x$ in $C$, or reports that $x \not\in C$.
Let $c(n)$ ...
- 28.2k
0
votes
Lower Bound on Parity of Boolean Functions
This is false, various construction for computing simultaneously the same function on disjoint sets of variables are discussed in this cstheory.stackoverflow question.
- 156
Top 50 recent answers are included