Most Popular
1500 questions
17
votes
2 answers
Better lower bounds than 3n for non-boolean functions?
Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related results.
What are the best known lower bounds if the…
Manu
- 7,659
- 3
- 37
- 42
17
votes
1 answer
Where's the Flaw in Blum-Feldman-Micali's Method
Blum, Micali, and Feldman (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some distribution (usually, uniform distribution) by…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
17
votes
3 answers
Complexity class separations without hierarchy theorems
Hierarchy theorems are fundamental tools. A good number of them was collected in an earlier question (see What hierarchies and/or hierarchy theorems do you know?). Some complexity class separations directly follow from hierarchy theorems. Examples…
Andras Farago
- 11,396
- 37
- 70
17
votes
2 answers
What parts of homotopy type theory are not possible in Agda or Coq?
When we look at the book, Homotopy Type Theory - we see the following topics:
Homotopy type theory
2.1 Types are higher groupoids
2.2 Functions are functors
2.3 Type families are fibrations
2.4 Homotopies and equivalences
2.5 The higher groupoid…
hawkeye
- 2,581
- 1
- 18
- 34
17
votes
4 answers
What would be the consequences of PH=PSPACE?
A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing plenty of reasons to believe $NP\neq PSPACE$.
What…
Andras Farago
- 11,396
- 37
- 70
17
votes
4 answers
Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs
I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs.
I've seen the question regarding the other way around here “Directed” problems that are easier than their “undirected”…
R B
- 9,448
- 5
- 34
- 74
17
votes
1 answer
Clique-width expressions with logarithmic depth
When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree decomposition where the tree is binary and its…
Michael Lampis
- 3,698
- 22
- 31
17
votes
2 answers
How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?
Unambiguous Finite Automatons (UFA) are special type of non-deterministic finite automatons (NFA).
A NFA is called unambiguous if every word $w\in \Sigma^*$ has at most one accepting path.
This means $DFA\subset UFA\subset NFA$.
Known related…
R B
- 9,448
- 5
- 34
- 74
17
votes
1 answer
Boolean Functions Where Sensitivity Equals Block Sensitivity
Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ is only polynomially larger than $s(f)$. What…
mhum
- 3,382
- 1
- 21
- 22
17
votes
2 answers
Linear diophantine equation in non-negative integers
There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative $x_1,x_2, ... , x_n$ to the equation $a_1 x_1 + a_2 x_2 +…
4evergr8ful
- 319
- 2
- 4
17
votes
1 answer
Career in Theoretical Computer Science
I am currently a high school student, interested in theoretical computer science and applied mathematics. I have self taught myself linear algebra and calculus and concrete mathematics. I have a naive notion that for one to write better algorithms,…
Iota
- 171
- 3
17
votes
1 answer
Completeness and Context-Sensitive Languages.
I'm interested in two questions regarding context-sensitive languages (CSL) and completeness:
Is there a notion of completeness for CSL, and which languages are complete?
Are there natural CSL that are NP-complete?
For 2., I can certainly think…
Michaël Cadilhac
- 3,946
- 22
- 39
17
votes
0 answers
Longest geometrically increasing subsequence
Given a sorted array of $n$ positive integers, the problem is to find the longest subsequence so that the progression of differences between consecutive elements of the subsequence is geometrically increasing.
Is there any complexity theoretic…
Simd
- 3,902
- 20
- 49
17
votes
0 answers
Tiling a rectangle with the fewest squares
Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares.
Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best known algorithm?
randomizer
- 741
- 5
- 15
17
votes
2 answers
Generalization of locally bounded treewidth graphs
Is the following graph class known in the literature?
The class of graphs is parameterized by positive integers $d$ and $t$ and contains each graph $G=(V,E)$ such that for each vertex $v\in V$, the subgraph of $G$ induced on all vertices at distance…
Serge Gaspers
- 5,116
- 29
- 42