Most Popular
1500 questions
25
votes
2 answers
How do you get the Calculus of Constructions from the other points in the Lambda Cube?
The CoC is said to be the culmination of all three dimensions of the Lambda Cube. This isn't apparent to me at all. I think I understand the individual dimensions, and the combination of any two seems to result in a relatively straightforward union…
sleepytea
- 353
- 3
- 6
25
votes
7 answers
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
László Babai recently proved that
the Graph Isomorphism problem is in quasipolynomial time.
See also his
talk at University of Chicago,
note from the talks by Jeremy Kun
GLL post 1,
GLL post 2,
GLL post 3.
According to Ladner’s theorem,
if $P \neq…
user17918
25
votes
3 answers
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?
Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" complexity aims to refine this qualitative distinction…
user17918
25
votes
2 answers
Is it decidable to determine if a given shape can tile the plane?
I know that it is undecidable to determine if a set of tiles can tile the plane,
a result of Berger using Wang tiles.
My question is whether it is also known to be undecidable to determine
if a single given tile can tile the plane, a monohedral…
Joseph O'Rourke
- 3,753
- 23
- 41
25
votes
1 answer
Is it still open to determine the complexity of computing the treewidth of planar graphs?
For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-hard. (Source).
However, when the input graph is…
a3nm
- 9,269
- 27
- 86
25
votes
1 answer
Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences
For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct integers $p_1, \ldots, p_n$, the sequence…
a3nm
- 9,269
- 27
- 86
25
votes
5 answers
Curious about computer-assisted NP-completeness proofs
In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that
This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework…
hengxin
- 2,329
- 1
- 17
- 32
25
votes
1 answer
Finding the smallest DFA that separates two words without using brute force search?
Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y. One way to do this is brute force search. You enumerate DFA's starting with the smallest. You try each DFA until you find one that accepts x and rejects…
Michael Wehar
- 5,127
- 1
- 24
- 54
25
votes
2 answers
What is the folk model of linear logic?
Probably the most common application of linear types in PL is to use them to give languages which control aliasing (i.e., a linear value has a single pointer to it, more or less).
But there's a slight mismatch between this usage and typical…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
25
votes
1 answer
Why is HAMILTONIAN CYCLE so different from PERMANENT?
A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a
polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such that…
Stasys
- 6,765
- 29
- 54
25
votes
5 answers
Are there any annotated formal verification systems for pure functional programming languages?
ACSL (Ansi C Specification Language), is a specification for C code, annotated with special comments, that allows C code to be formally verified.
I have not looked into it, but I imagine that the formal methods used in ACSL verifiers would be…
Nathan BeDell
- 603
- 4
- 10
25
votes
1 answer
$RL=L$ Progress Since 2006
Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (http://dl.acm.org/citation.cfm?id=1132583) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are not consistently labeled.
Has any further…
ruadath
- 441
- 3
- 9
25
votes
4 answers
Why do equalities between complexity classes translate upwards and not downwards?
Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the conversion (say from say $NP$ to $P$), which yields a…
gabgoh
- 1,548
- 12
- 22
25
votes
3 answers
Hardness of approximation - additive error
There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for vertex cover is optimal assuming UGC). This…
Simd
- 3,902
- 20
- 49
25
votes
3 answers
Nontrivial algorithm for computing a sliding window median
I need to calculate the running median:
Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$.
Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$.
(No cheating with approximations; I would…
Jukka Suomela
- 11,500
- 2
- 53
- 116