Most Popular
1500 questions
15
votes
2 answers
What's the complexity of Median-SAT?
Let $\varphi$ be a CNF formula with $n$ variables and $m$ clauses. Let $t \in \{ 0,1 \}^n$ represent a variable assignment and $f_{\varphi}(t) \in \{ 0, \ldots , m \}$ count the number of clauses satisfied by a variable assignment to $\varphi$.…
Huck Bennett
- 4,868
- 2
- 33
- 46
15
votes
3 answers
"Refined" list of open problems in TCS
In the conference on learning theory (COLT), a list of open problems is published every year, for example, the list of 2019.
The open problems are being submitted and peer reviewed, which makes this list reliable (in the sense that the problems are…
Johana T.
- 151
- 2
15
votes
1 answer
Which formal language class are XML and JSON with unique keys?
I moved this question from stackoverflow where id got no answers. We had a similar question whether JSON is regular:
JSON and XML are both frequently called to be context-free languages - they are both specified mainly by a formal grammar in EBNF.…
Jakob
- 1,259
- 11
- 16
15
votes
3 answers
Theories which characterize classes of computational complexity
When reading the paper "An applicative theory for FPH" you can encounter the following passage:
Considering theories which characterize classes of computational complexity, there are three different approaches:
in one, the functions which can be…
Oleksandr Bondarenko
- 4,215
- 1
- 25
- 46
15
votes
2 answers
Complexity lower bound: the gap between decision trees and RAMs
I recently discovered a quadratic lower bound on the complexity of a problem in the decision tree model, and I wonder whether this result could be partially generalized to the random access machine model. By partially, I mean a generalization to RAM…
Totoro
- 153
- 5
15
votes
2 answers
NP-hard problems with very fast exponential-time algorithms
NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare.
Is any fact like
"For any constant $\epsilon>0$ there is an NP-hard 'natural' problem $\Pi_{\epsilon}$ that is not solvable in…
vb le
- 4,828
- 1
- 37
- 46
15
votes
2 answers
Quantum analogues of SPACE complexity classes
We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in complexity theory there was much success with these…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
15
votes
3 answers
Super Mario Flows in NP?
One classical extension of the max-flow problem is the "max-flow over time" problem: you are given a digraph, two nodes of which are distinguished as the source and the sink, where each arc has two parameters, a capacity-per-unit-time and a delay.…
daveagp
- 1,100
- 7
- 14
15
votes
1 answer
Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?
I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ .
Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph of $P$?
(Polynomial in the dimension, the number…
Elle Najt
- 1,439
- 8
- 19
15
votes
1 answer
Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons
Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons?
Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem (update (2021): it is possible), but the average case…
Dmytro Taranovsky
- 2,577
- 1
- 10
- 24
15
votes
0 answers
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For example (a more formal treatment is below), a…
Dmytro Taranovsky
- 2,577
- 1
- 10
- 24
15
votes
2 answers
What are theoretical computer science jobs?
Beside academia which is clearly the home of theorists, I am wondering about industrial jobs related to theoretical computer science, the ones which demand pure mathematical background.
Cheers !
user46169
15
votes
1 answer
Examples of algorithms and proofs that seem correct, but aren't
In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an algorithm already known to be correct, is correct. We've…
Marin
- 153
- 5
15
votes
1 answer
Algorithms Design and Complexity - How to think in that 'way'?
My question is a general one: How do I start thinking in terms of Algorithm Design and Complexity? I am going to take a Graduate Course in Algorithm Design. I had enrolled in it earlier but dropped it later because I could not keep up with it. I…
Jason Dane
- 151
- 3
15
votes
1 answer
Entropy and computational complexity
There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, computational complexity $F(n) $ is correlated to…
XL _At_Here_There
- 1,070
- 7
- 17