Most Popular
1500 questions
17
votes
3 answers
Efficient logspace algorithms
It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, planar graph isomorphism) run in $O(n^k)$ where $k$…
Shiva Kintali
- 10,578
- 41
- 74
17
votes
2 answers
How to think about coherent spaces intuitively?
Linear Logic is interpreted using coherent spaces, and they feature prominently in Girard's papers. I know all the three main ways to formally define them, and they don't really pose any problem to use and prove stuff about, but I just can't…
valya
- 477
- 2
- 8
17
votes
0 answers
Deeper look at Algorithmica?
Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The first world presented is Algorithmica, in which…
András Salamon
- 19,000
- 3
- 64
- 150
17
votes
4 answers
Alternate notion of complexity based on gap between brute-force and the best algorithm?
Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space. This means that the problem must be easy in two senses: first, the problem can be solved in a polynomial number of steps, and second, the solution…
Ian
- 2,727
- 20
- 24
17
votes
1 answer
Permutations with forbidden subsequences
Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition.
Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a permutation
$\pi:[n]\rightarrow [n]$ of the set…
Mateus de Oliveira Oliveira
- 3,052
- 21
- 27
17
votes
1 answer
Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?
In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\epsilon$ moves aren't allowed, and the stack can…
Phylliida
- 1,132
- 5
- 22
17
votes
1 answer
smallest circuit size using XOR gates
Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables.
The goal is to compute the minimum number of XOR operations you need to perform to…
Mohammad R. Salavatipour
- 173
- 4
17
votes
3 answers
Finding witness in minkowski sum of integers
Let $A$ and $B$ be subsets of $\{0,\ldots,n\}$. We are interested in finding the Minkowski sum $A+B=\{a+b~|~a\in A,b\in B\}$.
$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ is a characteristic function of $X$ if $$\chi_X(x) = \begin{cases} 1 \text{ if } x\in…
Chao Xu
- 4,399
- 23
- 32
17
votes
0 answers
Can short-distance connectivity be harder than connectivity?
Has anybody seen the following (or similar) question being considered:
Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the
presence/absence of short $s$-$t$ paths?
A bit more formally, the distance-$k$…
Stasys
- 6,765
- 29
- 54
17
votes
3 answers
Are there any known implementations for quantum computing constructs?
Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the Church-Turing thesis).
What are the most…
Shane
- 2,233
- 3
- 26
- 25
17
votes
2 answers
Set Cover for Permutation Matrices
Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has at least 1 in every position?
I am interested in…
Brayden Ware
- 173
- 3
17
votes
2 answers
Cover Time of Directed Graphs
Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is known to be upper bounded by $O(n^3)$. There are…
Shiva Kintali
- 10,578
- 41
- 74
17
votes
1 answer
Degree sets for linear extension graphs
A linear extension $L$ of a poset $\mathcal{P}$ is a linear order on the
elements of $\mathcal{P}$, such that $x \leq y$ in $\mathcal{P}$ implies $x \leq y$ in $L$ for all $x,y\in\mathcal{P}$.
A linear extension graph is a graph on the set of linear…
Oleksandr Bondarenko
- 4,215
- 1
- 25
- 46
17
votes
1 answer
Online transitive closure better than O(N^2) per edge addition
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:
For every new edge u->v connect all nodes in Pred(u)…
Alexandru
- 696
- 3
- 16
17
votes
1 answer
Formalizing Homotopy Type theory in Idris
Looking at the homotopy type theory blog one can easily find a lot of library formalizing most of Homotopy Type Theory in Agda and Coq.
Is there anyone aware if there is any similar attempt to formalize HoTT in Idris?
Giorgio Mossa
- 454
- 2
- 10