Questions tagged [unary-languages]
The unary-languages tag has no usage guidance.
5
questions
12
votes
1answer
676 views
What is the simplest computational model for which the emptiness problem is undecidable?
What is the simplest computational model for which the emptiness problem is undecidable?
Emptiness problem for a computational model (e.g. finite state automaton, alternating pushdown automaton, ...
11
votes
1answer
283 views
Can one-way alternating automata with one-counter recognize some unary non-regular languages?
One-way alternating pushdown automata (1APDA) can recognize any language in $ DTIME(2^{O(n)}) $ (Alternation by Chandra, Kozen, and Stockmeyer, 1981). By replacing a pushdown storage of a 1APDA with a ...
8
votes
0answers
117 views
Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?
Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another.
However, if we consider larger complexity classes such as ...
3
votes
0answers
171 views
Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?
It is known that if any unary language is NP-complete, then P=NP.
Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying ...
0
votes
0answers
117 views
Complexity classes for problems that can be solved only from the length of the input
A tally language is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time).
...
