Most Popular
1500 questions
16
votes
2 answers
Faster join of treap-like data structures with approximately the same size
Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in $T_1$ and $T_2$ in time $O(1+|h(T_1) - h(T_2)|)$, where…
jbapple
- 11,184
- 2
- 29
- 50
16
votes
1 answer
Password hashing using NP complete problems
Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is DK = PBKDF2(HMAC, Password, Salt, ...). Because HMAC is a 2-round hashing…
Cyker
- 779
- 4
- 15
16
votes
2 answers
Minimum number of transpositions to sort a list
In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it. For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way to calculate the optimal number of…
sova
- 263
- 2
- 5
16
votes
1 answer
Probability that a random sorting network works
Given $n$ inputs $x_0, \ldots, x_{n-1}$, we construct a random sorting network with $m$ gates by iteratively picking two variables $x_i, x_j$ with $i < j$ and adding a comparator gate that swaps them if $x_i > x_j$.
Question 1: For fixed $n$, how…
Geoffrey Irving
- 3,253
- 15
- 29
16
votes
0 answers
Phase Transitions in NP Hard Problems
SAT Problems have a phase transition that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP Complete problems in general, AFAIK.
Suppose I have a…
Ganesh
- 521
- 3
- 9
16
votes
1 answer
Are innermost reductions perpetual in untyped λ-calculus?
(I have already asked this at MathOverflow, but got no answers there.)
Background
In the untyped lambda calculus, a term may contain many redexes, and different choices about which one to reduce may produce wildly different results (e.g. $(\lambda…
kow
- 163
- 4
16
votes
2 answers
What exactly are the classes FP, FNP and TFNP?
In his book Computational Complexity, Papadimitriou defines FNP as follows:
Suppose that $L$ is a language in NP. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced relation $R_L$ such that for all strings $x$: There is…
Auberon
- 313
- 2
- 8
16
votes
3 answers
Separating time classes
A student of mine recently ask the following question:
Assume $$DTIME(f(n)) \subsetneq DTIME(g(n)).$$ Must there exist an $h(n)$ such that $$DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))?$$
This could probably be shown true by…
S. Pek
- 423
- 2
- 8
16
votes
2 answers
Does Karp reducibility yield a total order?
Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?
Mal
- 355
- 1
- 5
16
votes
0 answers
What is the background in algebraic geometry and representation theory needed for geometric complexity theory?
I'm a mathematics student in my junior year and I'm interested in computational complexity and specially geometric complexity theory. I'm going to learn algebraic geometry and representation theory but I want to consider the parts that are related…
FNH
- 269
- 1
- 4
16
votes
1 answer
Relative consistency of PA and some type theories
For a type theory, by consistency, I mean that it has a type which is not inhabited. From the strong normalization of the lambda cube, it follows that system $F$ and system $F_\omega$ are consistent. MLTT + inductive types also has a normalization…
fhyve
- 343
- 1
- 5
16
votes
1 answer
Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?
It is a standard proof in automata courses that for $L = \Sigma^\star$ and $|\Sigma| \ge 2$ that $S(L) = \{ww : w \in L\}$ is not a context-free language.
It is also true that for any finite $L$, $S(L)$ is finite (and therefore a CFL). I'm guessing…
Ryan Dougherty
- 555
- 3
- 19
16
votes
2 answers
Time complexity of Bellman-Held-Karp algorithm for TSP, take 2
A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp. The algorithm is universally reported to run in $O(2^n n^2)$ time. However, as one of my students recently pointed…
Jeffε
- 23,129
- 10
- 96
- 163
16
votes
2 answers
Finding the largest set of points of limited diameter
Given points $p_1,\ldots,p_n$ in $\mathbb{R}^{d}$ and a distance $l$ find the
largest subset of these points such that the Euclidian distance of no
two of them exceeds $l$.
What is the complexity of this problem?
In the graph over the points which…
Marcus Ritt
- 1,450
- 14
- 21
16
votes
2 answers
Is there a well-defined division operation on finite automata?
Background:
Given two deterministic finite automata A and B, we form the product C by letting the states in C be the cartesian product of states in A and states in B. Then, we choose transitions, initial state, and final states so the language…
Whosyourjay
- 513
- 3
- 7