= 27d567bc2d48d9f40e9ccc20ea370b15)
cousin_it comments on Open Thread, September, 2010-- part 2 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (858)
Consider this problem: given positive integers a,b,c, are there positive integers x,y such that a*x*x+b*y=c? Amazingly, it is NP-complete. Can anyone explain to me how it manages to be complete?
References are provided at Math Overflow but since that presumably is where you got the problem, that probably doesn't help you.
I do know that pretty much any problem - an instance of SAT, for example - can be encoded as a diophantine equation problem. So, though I can't provide the proof you want, I am not particularly surprised.
No, I didn't get it from Math Overflow. Do you, by chance, have the Manders and Adleman paper as a pdf? All versions seem to be behind paywalls.
It's indeed clear to me that SAT instances can be encoded as diophantine equations, but the intuitively obvious encoding doesn't yield equations with such simple structure, does it?
I've found a copy. Have yet to read it so I don't myself know how it works...
Could you email it to me or put it online somewhere? My address is vladimir.slepnev@gmail.com .
ETA: received, thanks a lot!
Another Vladimir? The distribution of names on LW seems to be heavily biassed. I believe that of the people whose real names I am aware of here there are approximately as many people named Vladimir as there are people not so named.
Yeah, Emile called us interchangeable minions. I'd say we are noisy, but not especially numerous.
When I first observed this strange coincidence, I thought that 1. there are many Russians interested in mathematics and philosophy, and 2. Vladimir is a very common Russian male name. But now I checked it and saw that 2. is not really true. Do you have some idea in place of 2.? Some geographic or demographic subgroup of Russians?
Vladimir M is Croatian. So, instead of Russians, you should be looking for a subgroup of Slavs.
No, sorry, complexity theory is not something I am particularly interested in, though I have been following discussion of Vinay Deolalikar’s “Proof” at this blog
If that is clear to you, then you are way ahead of me here. Perhaps it has something to do with coding arbitrary diophantine problems into that simple three-parameter two-variable quadratic. But I don't know enough number theory to suggest how that might be possible.
This is an impressively simple NP-complete problem description.
One obvious point is that you can solve it in O(sqrt(c)lg k) time where k=max(a,b,c), just by trying all the values of x such that x^2<=c. But of course, in terms of the size of the inputs n, e.g. encoded in base2, n=O(log(k)), this enumeration takes O(sqrt(2)^(k)) time.
No, I (probably, given a reasonable time limit) can't. But wow. I didn't expect to see something that apparently simple NP-complete.