Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.num-analysis.independent

Topic: Prime Generalization Conjecture
Replies: 47   Last Post: Feb 8, 2014 8:41 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Guest

Watch Watch this User
Re: Musatov Prime Generalization Conjecture
Posted: Jun 30, 2009 7:01 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
> > > <115c718c-fe66-4a34-ac7c-02b57c508...@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 NP-complete 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
NP-hard 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 polynomial-time
Turing machine. That is,

P = {L:L = L(M) for some deterministic polynomial-time Turing machine
M}

where L(M) = \{ w\in\Sigma^{*}: M \text{ accepts } w \}

and a deterministic polynomial-time 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^{*}, \left|w
\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 \left|y\right|\in\;O(\left|x\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 polynomial-time. 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: NP-Complete

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 many-one reductions. Here a polynomial-time 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 NP-complete 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 NP-complete problems are
polynomial-time isomorphic -- i.e. between any two problems, there is
a one-to-one and onto Karp reduction. If that's true, the NP-complete
problems could be interpreted as mere "relabelings" of one another.

NP-complete problems are p-superterse 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,...,Fk-1 are all unsatisfiable then Fk is satisfiable"), then P =
NP.

--
Musatov


Date Subject Author
6/20/09
Read Prime Generalization Conjecture
MeAmI.org
6/20/09
Read Re: Prime Generalization Conjecture
Richard Heathfield
6/20/09
Read Re: Prime Generalization Conjecture
CBFalconer
6/21/09
Read Re: Prime Generalization Conjecture
Richard Heathfield
6/26/09
Read Re: Prime Generalization Conjecture
MeAmI.org
6/26/09
Read Re: Prime Generalization Conjecture
John H. Guillory
6/26/09
Read Re: Prime Generalization Conjecture
Guest
6/26/09
Read Re: Prime Generalization Conjecture
Richard Heathfield
6/27/09
Read Re: Prime Generalization Conjecture
Guest
6/27/09
Read Re: Prime Generalization Conjecture
Guest
6/27/09
Read Re: Prime Generalization Conjecture
Guest
6/29/09
Read Re: Prime Generalization Conjecture
Peter Nilsson
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Guest
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Alf P. Steinbach
6/30/09
Read Re: Prime Generalization Conjecture
Richard Heathfield
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Guest
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Dik T. Winter
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Richard Heathfield
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Guest
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Richard Heathfield
6/30/09
Read Re: Musatov Prime Generalization Conjecture
mike
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Richard Heathfield
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Guest
9/13/13
Read Re: Musatov Prime Generalization Conjecture
9/13/13
Read Re: Musatov Prime Generalization Conjecture
7/7/09
Read Re: Musatov Prime Generalization Conjecture
Constructive Truth
7/8/09
Read Re: Musatov Prime Generalization Conjecture
Alan Morgan
9/13/13
Read Re: Musatov Prime Generalization Conjecture
7/8/09
Read Re: Musatov Prime Generalization Conjecture
Guest
7/8/09
Read Re: Musatov Prime Generalization Conjecture
Guest
7/8/09
Read Re: Musatov Prime Generalization Conjecture
mike
7/8/09
Read Re: Musatov Prime Generalization Conjecture
Constructive Truth
7/8/09
Read Re: Musatov Prime Generalization Conjecture
Constructive Truth
7/12/09
Read Re: Musatov Prime Generalization Conjecture
mike
7/13/09
Read Re: Musatov Prime Generalization Conjecture
Guest
7/15/09
Read Re: Musatov Prime Generalization Conjecture
Guest
8/24/09
Read Musatov Prime 2 + 3
Guest
8/24/09
Read Musatov Prime 2 + 3
Guest
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Guest
6/30/09
Read Re: Musatov Prime Generalization Conjecture
Ed Prochak
6/20/09
Read Re: Prime Generalization Conjecture
William Elliot
6/20/09
Read Revised Prime Generalization Conjecture
Guest
6/20/09
Read Revised Prime Generalization Conjecture
Guest
6/20/09
Read Re: Prime Generalization Conjecture
Guest
6/20/09
Read Re: Prime Generalization Conjecture
Guest
6/20/09
Read Re: Prime Generalization Conjecture
Guest
2/8/14
Read Re: Prime Generalization Conjecture
9/13/13
Read Re: Prime Generalization Conjecture

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.