Questions tagged [unary-languages]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
1 answer
217 views

Counting the different subsets of nodes seen when iterating a subset through a directed graph

For a given directed graph $G = (V, E)$ (possibly with loops), and some $S\subseteq V$ define the operation $G(S) = \{ v\mid (u,v)\in E\text{ for some } u\in S \}$. Now consider the infinite sequence $...
alsips-cl's user avatar
  • 158
1 vote
0 answers
76 views

Consequences of a $Parity$ $P$-problem being reducible to a sparse language?

$Parity$ $P$ is the class where an $NP$-machine answers $YES$ if and only if the number of accepting paths of that turing machine is odd. With regards to the $P$ vs $NP$ question, there is a theorem ...
user avatar
5 votes
1 answer
638 views

Unary language examples between L and NP

I am looking for some examples of unary languages lay between $L$ and $NP$, i.e., $ L \subseteq NL \subseteq P = AL \subseteq NP $. What I found after some search(e.g., Complexity zoo for unary ...
Abuzer Yakaryilmaz's user avatar
8 votes
0 answers
148 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 ...
Hans Schmuber's user avatar
3 votes
0 answers
370 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 ...
Hans Schmuber's user avatar
0 votes
0 answers
139 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). ...
a3nm's user avatar
  • 9,259
12 votes
1 answer
874 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, ...
Abuzer Yakaryilmaz's user avatar
11 votes
1 answer
319 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 ...
Abuzer Yakaryilmaz's user avatar