Circuit Satisfiability Problem for circuits of small complexity

Marsel Matdinov

The following problem is considered. A Turing machine $M$, that accepts a string of fixed length $t$ as input, runs for a time not exceeding a fixed value $n$ and is guaranteed to…