Most Popular
1500 questions
19
votes
0 answers
Courcelle's theorem for bounded clique-width graphs
Courcelle's theorem states that "Every graph property which is expressible in monadic second order logic is decidable in linear time for bounded tree-width graphs". Later it was extended to bounded clique-width graphs [CMR99].
The theorem also…
Kumar
- 2,044
- 13
- 27
19
votes
4 answers
Applications of Complexity Theory
Complexity theory seems to capture something fundamental about the
structure of the universe, in that it formalizes the intuitive notion
that some problems are harder than others.
Scott Aaronson predicted, "The NP Hardness Assumption will eventually…
rphv
- 583
- 3
- 11
19
votes
2 answers
What do we know about restricted versions of the halting problem
(UPDATE: a better formed question is posed here as the comments for the accepted answer below show that this question is not well-defined)
The classical proof of the impossibility of the halting problem depends on demonstrating a contradiction when…
Mohammad Alaggan
- 1,812
- 18
- 29
19
votes
1 answer
Algorithmic advantages of pathwidth over treewidth
Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth $k$, it also has treewidth at most $k$, while in…
Michael Lampis
- 3,698
- 22
- 31
19
votes
1 answer
Scott's stochastic lambda calculi
Recently, Dana Scott proposed stochastic lambda calculus, an attempt to introduce probabilistic elements into (untyped) lambda calculus based on a semantics called graph model. You can find his slides on line for example here and his paper in…
Pteromys
- 895
- 4
- 13
19
votes
0 answers
Lower bounds on single-source shortest paths in directed graphs
Are there any non-trivial lower bounds on the complexity of single-source shortest paths (SSSP) in a directed graph, where all edges have non-negative edge weights? Can we rule out the possibility of an algorithm with $O(n+m)$ running time? Are…
D.W.
- 12,054
- 2
- 34
- 80
19
votes
3 answers
What separates easy global problems from hard global problems on graphs of bounded treewidth?
Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a local problem is a problem whose solution can be…
Juho
- 3,170
- 2
- 26
- 36
19
votes
3 answers
What is the expected depth of a randomly generated tree?
I thought about this problem a long time ago, but have no ideas about it.
The generating algorithm is as follows. We assume there are $n$ discrete nodes numbered from $0$ to $n - 1$. Then for each $i$ in $\{1, \dotsc, n - 1\}$, we make the $i$th…
zhxchen17
- 293
- 1
- 7
19
votes
2 answers
Quantum algorithms based on transforms other than Fourier transforms
In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier transforms and suggests that invariance properties of…
Sam Burville
- 495
- 3
- 8
19
votes
1 answer
Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?
Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?
I know it is NP-complete for the class of planar graphs of maximum degree 3 (see the…
Florent Foucaud
- 2,153
- 12
- 27
19
votes
1 answer
The Warren Buffett Problem
Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any related work, I would appreciate references.
The…
Martin Pál
- 591
- 3
- 8
19
votes
2 answers
"Tiny" Graph Isomorphism
While thinking about the complexity of testing isomorphism of asymmetric graphs (see my related question on cstheory), a complementary question came to my mind.
Suppose that we have a polynomial time Turing machine $M$ that on input $1^n$ generates…
Marzio De Biasi
- 22,915
- 2
- 58
- 127
19
votes
2 answers
Problems with efficient solution except for a small fraction of inputs
The halting problem for Turing machines is perhaps the canonical undecidable
set. Nevertheless, we prove that there is an algorithm deciding almost
all instances of it. The halting problem is therefore among the growing collection
of those…
Jim Graber
- 357
- 1
- 5
19
votes
1 answer
Conjecture about two counters automata
I would like to prove (or disprove) the following conjecture:
Conjecture: a two counter automata (2CA) cannot decide the following language:
$L = \{ n \mid $ the ternary and binary representations of $n$ have both even length or odd length$\}$
A 2CA…
Marzio De Biasi
- 22,915
- 2
- 58
- 127
19
votes
1 answer
Natural candidate against the Isomorphism Conjecture?
The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is that it implies $P\neq NP$. It was published in…
Andras Farago
- 11,396
- 37
- 70