Bjørn Kjos-Hanssen

Search

Primary Menu

Skip to content

Bjørn Kjos-Hanssen
Posts
Publications
Software
Teaching
Calendar

Search for:

Complexity guessing game

$011001111100$ (length 12)

Your guess for its complexity, from 1 to 7:
Your name:

Q&A

Computability.org
CS Theory
MathOverflow
Quant
Stats

Professor of Mathematics, University of Hawaii at Manoa

About the Complexity Guessing Game

The complexity $A_N(x)$ of a string $x$ of length $n$ in this game is the minimum number of states of a nondeterministic finite state automaton, accepting $x$, that accepts along only one path of length $n$.

Complexity guessing game

Buy the app
High score table
Hyde and Kjos-Hanssen, Electronic Journal of Combinatorics 2015

Powered by WordPress