$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?


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.