Most Popular
1500 questions
21
votes
7 answers
Golden ratio or Pi in the running time
There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.
Plummer
- 401
- 2
- 6
21
votes
2 answers
Recognizing line graphs of hypergraphs
The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection.
A hypergraph is an $r$-hypergraph if each of its edges has at most $r$…
user13136
- 2,477
- 1
- 24
- 24
21
votes
2 answers
What are the #P-complete subfamilies of #2-SAT?
Short version.
The original proof that #2-SAT is #P-complete shows, in fact, that those instances of #2-SAT which are both monotone (not involving the negations of any variables) and bipartite (the graph formed by the clauses over the variables is a…
Niel de Beaudrap
- 8,821
- 31
- 70
21
votes
5 answers
Reasons for which a graph may be not $k$ colorable?
While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to identify so far:
$G$ contains a clique of size…
Giorgio Camerani
- 6,842
- 1
- 34
- 64
21
votes
2 answers
Element distinctness in O(n) time?
We all know that element distinctness in the comparison based model cannot be done in $o(n\log n)$ time. However, on a word-RAM, one can possibly achieve better.
Of course, if one assumes the existence of a perfect hash function that can be computed…
Vinayak Pathak
- 1,631
- 10
- 22
21
votes
10 answers
#SAT Solver download
Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an approximation.
Giorgio Camerani
- 6,842
- 1
- 34
- 64
21
votes
4 answers
Language and automata textbook, free or low cost?
I'll be teaching a standard undergraduate class on languages and automata next semester, and would prefer to use a legitimate free or low-cost text. Any suggestions?
I love the Sipser text but the latest edition costs $196, which is hard to say with…
Kevin A. Wortman
- 383
- 1
- 6
21
votes
2 answers
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is poly-time solvable for degree-$3$ bounded graphs and…
Davis Issac
- 368
- 1
- 9
21
votes
1 answer
Approximate 1d TSP with linear comparisons?
The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way that approximation as well as exact solution makes…
David Eppstein
- 50,990
- 3
- 170
- 278
21
votes
0 answers
Descriptive complexity characterization of TimeSpace classes
Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?
Kaveh
- 21,577
- 8
- 82
- 183
21
votes
1 answer
What are some careers in theoretical computer science that do not require a PhD?
I am an undergraduate, and have recently come to terms with the fact that I may not have the intellect to do research in theoretical computer science, or be able to be admitted into and complete a PhD program. However, I would still like to be…
user10240
- 319
- 2
- 3
21
votes
2 answers
Can addition be carried out in less than depth 5?
Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary numbers using a polynomial size circuit family with…
Anonymous
- 4,041
- 19
- 43
21
votes
3 answers
Are recursive forms of Godel's statement possible?
The self-referentiality of the P/NP problem has sometimes been highlighted as a barrier to its resolution, see, for instance, Scott Aaronson's paper, is P vs. NP formally independent? One of the many conceivable resolutions to P/NP would be a…
Anand Kulkarni
- 853
- 6
- 15
20
votes
2 answers
Super-polynomial time approximation algorithms for MAX 3SAT
The PCP theorem states that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.
There is a trivial polynomial time algorithm that satisfies $7/8$…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
20
votes
6 answers
SAT algorithms not based on DPLL
Are there any algorithms for SAT solving which are not DPLL based?
Or are all algorithms used by SAT solvers are DPLL based?
Anonymous
- 4,041
- 19
- 43