Mathematics – Number Theory
Scientific paper
2006-11-08
Mathematics
Number Theory
52 pages; long version of 1979 FOCS conference paper; v2 added material to introduction, 62 pages
Scientific paper
Binary quadratic Diophantine equations are of interest from the viewpoint of computational complexity theory. They contain as special cases many examples of natural problems apparantly occupying intermediate stages in the P-NP hierarchy, i.e. problems neither known to be polynomial time or NP-complete. Let L(F) denote the length of the binary encoding of the coefficients of a binary quadratic diophantine equation F(x_1, x_2)=0. This paper shows there is a certificate of length polynomial in L(F) that such an equation has an integer solution (resp. positive integer solution) when one exists. This is interesting because it is known there exist such equations whose minimal nonnegative integer solution is so large that it requires space exponential in L(F) to write it down in binary representation. The certificates are based on the ideas of D. Shank's "infrastructure".
No associations
LandOfFree
Succinct certificates for solutions to binary quadratic Diophantine equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Succinct certificates for solutions to binary quadratic Diophantine equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct certificates for solutions to binary quadratic Diophantine equations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-625567