This paper deals with the question of developing faster probabilistic methods for solving NP problems. Here polynomial bounds will mean bounds which are polynomials in the number of binary inputs needed to specify an NP problem. It is known that such there are NP-complete problems consisting of a system of a pair of diophantine (polynomial) equations of at most polynomial degree in at most polynomially many variables which are to be rational functions (quotients of polynomials) in one variable t. This means those variables lie in a function K(t) where K can be a global field or its algebraic closure. Solving this problem is equivalent to finding a section of a map \(\pi \) from an algebraic variety V to projective space CP of dimension 1. This can be studied in terms of the Schottky problem for a branched covering of low degree of V. The Schottky problem is to determine whether an abelian variety is the Jacobian of a curve. We propose a probabilistic algorithm for this problem which could be done by parallel computation on classical computers. This is a theoretical paper and we do not have numerical data, but it is possible that this algorithm could be carried out in polynomial time.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Randomized Algorithms for NP Problems and the Schottky Problem

  • Fred W. Roush

摘要

This paper deals with the question of developing faster probabilistic methods for solving NP problems. Here polynomial bounds will mean bounds which are polynomials in the number of binary inputs needed to specify an NP problem. It is known that such there are NP-complete problems consisting of a system of a pair of diophantine (polynomial) equations of at most polynomial degree in at most polynomially many variables which are to be rational functions (quotients of polynomials) in one variable t. This means those variables lie in a function K(t) where K can be a global field or its algebraic closure. Solving this problem is equivalent to finding a section of a map \(\pi \) from an algebraic variety V to projective space CP of dimension 1. This can be studied in terms of the Schottky problem for a branched covering of low degree of V. The Schottky problem is to determine whether an abelian variety is the Jacobian of a curve. We propose a probabilistic algorithm for this problem which could be done by parallel computation on classical computers. This is a theoretical paper and we do not have numerical data, but it is possible that this algorithm could be carried out in polynomial time.