
Re: Musatov Prime Generalization Conjecture
Posted:
Jun 30, 2009 7:01 PM


On Jun 30, 3:36 pm, mike <m....@irl.cri.replacethiswithnz> wrote: > In article <_9qdnbY6rMCzjdfXnZ2dnUVZ8tZi4...@bt.com>, > r...@see.sig.invalid says... > > > > > Dik T. Winter said: > > > > In article > > > <115c718cfe664a34ac7c02b57c508...@i6g2000yqj.googlegroups.com> > > > Musatov <marty.musa...@gmail.com> writes: ... > > > <snip> > > > > > Shown: > > > > 2*4+1=9+2=11 prime > > > > 2*24+1=49+2=51 prime > > > > Since when is 51 prime? > > > It's odd, right? And primes (ignoring 2, which is clearly > > experimental error) are odd, right? Therefore, 51 is prime, QED. > > Come now Richard, you have to ignore 3 and 17 as well to prove that 51 > is prime. > > Mike Hide quoted text  > >  Show quoted text 
If it is known that if any NPcomplete language is sparse (contains no more than a polynomial number of strings of length n), then P = NP. [BH08] improved this result, showing that if any language in NP has an NPhard set of subexponential density, then coNP is contained in NP/ poly and thus, by [Yap82], PH collapses to the third level. Conceptually, a decision problem is a problem that takes as input some string, and outputs "yes" or "no". If there is an algorithm (say a Turing machine, or a computer program with unbounded memory) which is able to produce the correct answer for any input string of length Failed to parse (<math_output_error>): n
in at most c \cdot n^k steps, where k and Failed to parse (<math_output_error>): c are constants independent of the input string, then we say that the problem can be solved in polynomial time and we place it in the class P. Formally, P is defined as the set of all languages which can be decided by a deterministic polynomialtime Turing machine. That is,
P = {L:L = L(M) for some deterministic polynomialtime Turing machine M}
where L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}
and a deterministic polynomialtime Turing machine is a deterministic Turing machine M which satisfies the following two conditions:
1. M halts on all input w; and 2. there exists k \in N such that T_{M}(n)\in\; O(nk),
where T_{M}(n) = \max\{ t_{M}(w) : w\in\Sigma^{*}, \leftw \right = n \} and tM(w) = number of steps M takes to halt on input w.
NP can be defined similarly using nondeterministic Turing machines (the traditional way). However, a modern approach to define NP is to use the concept of certificate and verifier. Formally, NP is defined as the set of languages over a finite alphabet that have a verifier that runs in polynomial time, where the notion of "verifier" is defined as follows.
Let Failed to parse (<math_output_error>): L
be a language over a finite alphabet, ?.
L\in\mathbf{NP} if, and only if, there exists a binary relation R \subset\Sigma^{*}\times\Sigma^{*} and a positive integer k such that the following two conditions are satisfied:
1. For all x\in\Sigma^{*}, x\in L \Leftrightarrow\exists y\in\Sigma^ {*} such that (x,y)\in R\; and \lefty\right\in\;O(\leftx\right^ {k}); and 2. the language L_{R} = \{ x\# y:(x,y)\in R\} over \Sigma\cup\{\#\} is decidable by a Turing machine in polynomial time.
A Turing machine that decides LR is called a verifier for L and a y such that (x,y)\in R is called a certificate of membership of x in L.
In general, a verifier does not have to be polynomialtime. However, for L to be in NP, there must be a verifier that runs in polynomial time. MartinMichaelMusatov 07:18, 24 February 2009 (UTC) NPC: NPComplete
The class of decision problems such that (1) they're in NP and (2) every problem in NP is reducible to them (under some notion of reduction). In other words, the hardest problems in NP.
Two notions of reduction from problem A to problem B are usually considered:
1. Karp or manyone reductions. Here a polynomialtime algorithm is given as input an instance of problem A, and must produce as output an instance of problem B. 2. Turing reductions, in this context also called Cook reductions. Here the algorithm for problem B can make arbitrarily many calls to an oracle for problem A.
Some examples of NPcomplete problems are discussed under the entry for NP.
The classic reference on NPC is [GJ79].
Unless P = NP, NPC does not contain any sparse problems: that is, problems such that the number of 'yes' instances of size n is upper bounded by a polynomial in n [Mah82].
A famous conjecture [BH77] asserts that all NPcomplete problems are polynomialtime isomorphic  i.e. between any two problems, there is a onetoone and onto Karp reduction. If that's true, the NPcomplete problems could be interpreted as mere "relabelings" of one another.
NPcomplete problems are psuperterse unless P = NP [BKS95]. This means that, given k Boolean formulas F1,...,Fk, if you can rule out even one of the 2k possibilities in polynomial time (e.g., "if F1,...,Fk1 are all unsatisfiable then Fk is satisfiable"), then P = NP.
 Musatov

