Most Popular
1500 questions
26
votes
1 answer
An edge partitioning problem on cubic graphs
Has the complexity of the following problem been studied?
Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$
Question: is there a partition of $E$ into $|E|/3$ parts of size $3$ such that the sum of the orders of the…
Anthony Labarre
- 3,264
- 1
- 25
- 33
26
votes
1 answer
Rabin–Karp vs Karp–Rabin
The wise other editors at Wikipedia have declined my request to move the Wikipedia article on the Rabin–Karp algorithm to what I think it should be called, the Karp–Rabin algorithm, on the basis that the Rabin–Karp name is used more often (false, if…
David Eppstein
- 50,990
- 3
- 170
- 278
26
votes
3 answers
Has there been any research on $k$-SAT above the satisfiability threshold?
A well known characteristic of $k$-SAT instances is the ratio of the number of clauses $m$ over the number of variables $n$, i.e., the quotient $\rho = m/n$. For every $k$, there is a threshold value $\alpha$ s.t.\ for $\rho \ll \alpha$, most…
Matt Groff
- 2,100
- 13
- 19
26
votes
3 answers
Optimization problems with minimax characterization, but no polynomial-time algorithm
Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the maximum value of $f(x)$ over $n$-bit strings…
Andras Farago
- 11,396
- 37
- 70
26
votes
3 answers
Is Magic: the Gathering Turing complete?
A very specific question, I'm aware, and I doubt it will be answered by anyone that isn't already familiar with the rules of Magic. Cross-posted to Draw3Cards. Here are the comprehensive rules for the game Magic: the Gathering. See this question for…
ripper234
- 873
- 10
- 15
26
votes
3 answers
Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1
Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\mathbb{Z}$). Is this problem NP-hard?
It is…
user17100
26
votes
3 answers
Consequences of #P = FP
Which would be the consequences of #P = FP?
I'm interested in both practical and theoretical consequences.
From a practical point of view, I'm particularly interested in consequences on Artificial Intelligence.
Pointers to papers or books are more…
Giorgio Camerani
- 6,842
- 1
- 34
- 64
26
votes
6 answers
Advanced techniques for determining complexity lower bounds
Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level.
Beyond the "simpler" techniques, such as reducing to sorting or an…
Joey Eremondi
- 2,832
- 15
- 29
26
votes
1 answer
Is $AC^0$ with bounded fanout weaker than $AC^0$?
In the survey "Small Depth Quantum Circuits" by D. Bera, F. Green and S. Homer (p. 36 of ACM SIGACT News, June 2007 vol. 38, no. 2), I read the following sentence:
The classical version of $QAC^0$ (in which $AND$ and $OR$ gates have at most…
Alessandro Cosentino
- 4,000
- 35
- 43
26
votes
4 answers
Separating Logspace from Polynomial time
It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$, $LogCFL$, $NC^i$, $SAC^i$, $AC^i$, $SC^i$. It…
Shiva Kintali
- 10,578
- 41
- 74
26
votes
4 answers
When does (or should) Theoretical CS care about intuitionistic proofs?
From what I understand (which is very little, so please correct me where I err!), theory of programming languages is often concerned with "intuitionistic" proofs. In my own interpretation, the approach requires us to take seriously the consequences…
usul
- 7,615
- 1
- 26
- 45
26
votes
2 answers
Universal Approximation Theorem — Neural Networks
I posted this earlier on MSE, but it was suggested that here may be a better place to ask.
Universal approximation theorem states that "the standard multilayer feed-forward network with a single hidden layer, which contains finite number of hidden…
Matt Munson
- 503
- 1
- 5
- 10
26
votes
6 answers
Can one return to a TCS research job after an excursion to a non-research industry job?
I have heard from some senior researchers in theoretical computer science that working in a non-research industry job, even just for a few years, will kill your career as a TCS researcher.
However I am suspicious of the claim that the road from…
Holger
- 975
- 9
- 17
26
votes
3 answers
Intermediate problems between L and NL
It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \cap coUL$. Cho and Huynh defined a parametrized…
Shiva Kintali
- 10,578
- 41
- 74
26
votes
4 answers
DFA intersection in subquadratic space?
The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the resulting minimal DFA has z states, where z=O(n), can…
Rasmus Pagh
- 962
- 6
- 11