0
$\begingroup$

$P$ is the polynomial time class defined as $$\cup_{i=0}^{\infty}DTIME(n^i).$$ which has linear programming as complete problem.

Are there complete problems under linear time reductions within each $DTIME(n^i)$ which come from some restricted form of linear programming or circuit evaluation problem?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.