Most Popular
1500 questions
18
votes
1 answer
Context-sensitive grammar for SAT?
By a classic result of Kuroda, the complexity class NSPACE[$n$] (also known as NLIN-SPACE) is precisely the class CSL of context-sensitive languages. The satisfiability problem SAT is in NSPACE[$n$], since a linear-sized guess for a solution can be…
András Salamon
- 19,000
- 3
- 64
- 150
18
votes
2 answers
Finite automata that accept binary strings divisible by n
I'm working on a problem set for a class, and thought of a question related to what I was working on. Is there a minimum number of states that a finite automaton must have in order to accept binary strings that represent numbers divisible by an…
Nick Van Hoogenstyn
- 309
- 2
- 6
18
votes
3 answers
What is the minimal extension of FO that captures the class of regular languages?
Context: relations between logic and automata
Büchi's Theorem states that Monadic Second Order logic over strings (MSO) captures the class of regular languages. The proof actually shows that existential MSO ($\exists\text{MSO}$ or EMSO) over strings…
Janoma
- 1,406
- 11
- 27
18
votes
4 answers
List of theorems stating that P does not equal NP if and only if
I think it would be a good idea to make a list of theorems stating that P does not equal NP if and only if such and such exits, some complexity class is contained in another complexity class and so on and so forth.
Tayfun Pay
- 2,598
- 2
- 18
- 45
18
votes
3 answers
Solving Superstring Exactly
What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?
UPD:
$O^*(\cdot)$ suppresses polynomial…
Alex Golovnev
- 2,247
- 1
- 20
- 23
18
votes
1 answer
Complexity of a switch network problem
A switch network (the name is invented) is made with three types of nodes:
one Start node
one End node
one or more Switch nodes
The switch node has 3 exits: Left, Up, Right; has two states L and R and
a target state TL or TR. Each switch can be…
Marzio De Biasi
- 22,915
- 2
- 58
- 127
18
votes
1 answer
Ranking the Difficulty of NP Hard Problems in Practice
This question is tightly related to another post: Phase Transitions in NP Hard Problems but it is somewhat different. While that question is about the hardness of particular instances of NP hard problems, this is about ranking the difficulty of the…
Carlos Linares López
- 584
- 3
- 13
18
votes
0 answers
Descriptive complexity of communication complexity classes
It is well known that some major complexity classes, like P or NP, admit a full logical characterization (e.g NP = existential 2nd order logic by Fagin's theorem). On the other hand, one can also define complexity classes in communication complexity…
Marcin Kotowski
- 2,806
- 19
- 25
18
votes
4 answers
Automated theorem proving in linear logic
Is automatic theorem proving and proof searching easier in linear and other propositional substructural logics which lack contraction?
Where can I read more about automatic theorem proving in these logics and the role of contraction in proof…
Anonymous
- 4,041
- 19
- 43
18
votes
2 answers
Uses of XORification
XORification is the technique to make a Boolean function or formula harder by replacing every variable $x$ by the XOR of $k\geq 2$ distinct variables $x_1 \oplus \ldots \oplus x_k$.
I am aware of uses of this technique in proof complexity, mainly…
Jan Johannsen
- 4,630
- 2
- 33
- 50
18
votes
1 answer
What is the best approximation for majority vote?
The majority vote operation comes up fairly often in fault-tolerance (and no doubt other places), where the function outputs a bit equal to which ever value appears most frequently in the value of the input bits. For simplicity, let's assume that…
Joe Fitzsimons
- 13,675
- 47
- 91
18
votes
2 answers
What persistent data structure for a set of partially ordered elements?
I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.
One problem with hashtables is that two equal elements can be represented differently, and I do…
Abdallah
- 803
- 5
- 12
18
votes
2 answers
Complexity of computing the discrete Fourier transform?
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?
The classical algorithm for fast Fourier transforms, inappropriately[1] attributed to Cooley and Tukey, is usually…
Jeffε
- 23,129
- 10
- 96
- 163
18
votes
4 answers
Consequences of $NP=coNP$ and $P\ne NP$?
We know that if $P=NP$ then the whole PH collapses.
What if the polynomial hierarchy collapses partially ? (Or how to understand that PH could collapse above a certain point and not below ?)
In shorter words, what would be the consequences of…
Xavier Labouze
- 1,117
- 1
- 9
- 27
18
votes
1 answer
Universal Function approximation
It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function.
What other models are there that are also universal function…
Opt
- 1,311
- 14
- 20