If NP has polynomial-size circuits, then MA = AM

Author： Arvind V.   Kobler J.   Schoning U.   Schuler R.  

Publisher： Elsevier

ISSN： 0304-3975

Source： Theoretical Computer Science, Vol.137, Iss.2, 1995-01, pp. : 279-282

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Related content

AM exp &unknown;(NP&unknown;coNP)/poly

By Vinodchandran N.V.  

Information Processing Letters, Vol. 89, Iss. 1, 2004-01 ,pp. : 43-47

Elsevier

Access to resources Recommend Favorite

Approximating SVP ~ to within almost-polynomial factors is NP-hard

By Dinur I.  

Theoretical Computer Science, Vol. 285, Iss. 1, 2002-08 ,pp. : 55-71

Elsevier

Access to resources Recommend Favorite

Polynomial Kernelizations for MIN F+Π1 and MAX NP

By Kratsch Stefan  

Algorithmica, Vol. 63, Iss. 1-2, 2012-06 ,pp. : 532-550

Springer Publishing Company

Access to resources Recommend Favorite

MAX3SAT is exponentially hard to approximate if NP has positive dimension

By M. Hitchcock J.  

Theoretical Computer Science, Vol. 289, Iss. 1, 2002-10 ,pp. : 861-869

Elsevier

Access to resources Recommend Favorite

A polynomial-time computable curve whose interior has a nonrecursive measure

By P. Young   Ko K.-I.  

Theoretical Computer Science, Vol. 145, Iss. 1, 1995-07 ,pp. : 241-270

Elsevier

Access to resources Recommend Favorite