Innovation, my TSP algorithm and factoring, timelines

On Aug 23, 1:16*pm, rossum <rossu...@coldmail.com> wrote:
> On Sat, 23 Aug 2008 12:05:31 -0700 (PDT), amor...@xenon.Stanford.EDU
>
>
>
> (Alan Morgan) wrote:
> >In article <fbaec2b7-e8a6-4562-9152-44400ccbe...@i24g2000prf.googlegroups.com>,
> >JSH *<jst...@gmail.com> wrote:
> >>On Aug 22, 7:39=A0pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> >>> JSH wrote:
> >>> > The Internet still uses public key encryption.
>
> >>> Public key encryption does not equal RSA or other factoring. As I've
> >>> said before, there's elliptic curve; there are other even more secure
> >>> algorithms.
>
> >>> > If P=3DNP, then a polynomial time solution is possible for factoring
> >>> > meaning that public key encryption is no longer viable as a security
> >>> > system.
>
> >>> No, it just means you have to keep bumping up key sizes every few years.
>
> >>Not with anything that would follow from my research.
>
> >>If what I call surrogate factoring is viable then public key
> >>encryption is dead.
>
> >>People could literally crack public keys in seconds on a desktop,
>
> >Depends on the key size and on the nature of the algorithm. *If
> >factoring turns out to be O(n^5000000) then P=NP, but I don't see
> >that causing many practical problems. *Even if it is something more
> >tractable you can just crank the key size through the roof.

My research approach to factoring has been towards finding something
that would be faster than public key use, which I'm worried now can be
achieved--if the research is correct.

So, regardless of the size of the public key, it could be factored
faster than it could be used.

> >Alan
>
> Or switch from RSA-Public Key to El Gamal-Public Key. *There are many
> different versions of Public Key, of which only a subset depend on the
> difficulty of factoring.
>
> rossum

But if P=NP then there are polynomial time solutions out there for ANY
of them.

That's why I think the research community has resisted any claims of
proof of P=NP, for political and economic reasons, so that people
would use these systems without fear that down the line--out of the
blue--they could be completely cracked.

Possibly they have believed like the poster Alan Morgan that even if
factoring can fall to a polynomial time solution, it'd be a very slow
one, so they can rationalize their behavior as not being threatening
to security.

In considering my own latest research with the optimal path engine,
however, if it is correct then they are very, very, very wrong, and if
P=NP then super fast algorithms are possible that would make one way
systems non-viable.

That could have military implications as well if I'm reading some info
correctly that <gasp> the military has also thought to use one way
systems as well, though I'm not sure on that one, as I don't know
really what military agencies do for encryption.


James Harris

JSH wrote:
> Possibly they have believed like the poster Alan Morgan that even if
> factoring can fall to a polynomial time solution, it'd be a very slow
> one, so they can rationalize their behavior as not being threatening
> to security.

You seem to be missing one key fact about NP-complete algorithms. Any NP
problem may be convertible to an NP-complete problem, but the conversion
is typically expensive.

Here's an example. I wrote a Turing machine to add two numbers. Five
state, four symbol. It takes O(3*n lg n) (where n is the number of bits
of the larger number) (the constant may be higher, I did the math well
over a year ago and I never checked it) steps and uses up O(2*n) slots
(I'm throwing in some constants here).

By Cook's Theorem, the SAT query will then O(30*n^2 lg n + 15*n lg n)
variables and a few hundred times that number of clauses, let's say 100.

Transforming to clique, we get the multiplication of these two number of
nodes and a triangular (i.e. 1/2n^2) number of edges for nodes. Up to
O(3000*n^4 lg n) nodes/O(4500000n^8 lg^2 n) edges.

Converting to vertex cover just takes the complement of the graph, so
node size stays the same and the edge size should still stay roughly the
same size.

We now construct a graph with the node size that is twice the number of
nodes times the average degree, which should be about N/2 by this point,
or another triangular relationship, plus the number of edges, so that
we get to about O(9e6*n^8 lg^2 n) nodes. The number of edges by this
point becomes too difficult to explain, but, naturally, it's even larger.

This graph we solve for the existence of a directed Hamiltonian circuit;
triple the number of nodes and make the number of edges equal to 2 *
old_node + old_edge for an undirected Hamiltonian circuit.

So far, everything was from Karp's paper; since he doesn't mention TSP
as NP-complete, I'm shifting to another resource for the TSP graph
construction.

Here, we keep the node graph and make each edge 1 if it exists in our
previous graph or 2 if it didn't (so the edges from the last part don't
matter).

So, even if we had an O(|V|^5) algorithm for generic TSP with a low
constant, our small O(3*n lg n) algorithm becomes
O(1.4e37*n^40 lg^10 n) if we attempt to use the algorithm based on the
various proofs of NP-completeness. Remember, this is only a 5-state,
4-symbol Turing machine.

Also, this doesn't take into account the actions you have to take to
*unroll* all the conversions.

Finally, these are based on reductions of *decision* problems, but
actually solving it is a different class of problem. I believe the
function problem equivalents should have identical reductions, though.

My tortured point is this: most proofs that an algorithm is NP-complete
do so by taking a pre-existing NP-complete algorithm and roughly
squaring its complexity (or worse!). So even though the algorithm is
polynomial, since it's been forced through many successive stages of
conversion, it becomes intractable.

So, here's my challenge to you: show us how to construct a graph such
that it's TSP solution factors the number.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

In article <g8pn1r$jk$1@xenon.Stanford.EDU>,
amorgan@xenon.Stanford.EDU (Alan Morgan) wrote:

> Depends on the key size and on the nature of the algorithm. If
> factoring turns out to be O(n^5000000) then P=NP, but I don't see
> that causing many practical problems. Even if it is something more

I thought that it wasn't known exactly what complexity class integer
factorization is in, and so a polynomial time algorithm for it would not
imply P=NP. Have I missed a development here, or am I misremembering?

--
--Tim Smith

On Aug 23, 4:52*pm, Tim Smith <reply_in_gr...@mouse-potato.com> wrote:
> In article <g8pn1r$j...@xenon.Stanford.EDU>,
> *amor...@xenon.Stanford.EDU (Alan Morgan) wrote:
>
> > Depends on the key size and on the nature of the algorithm. *If
> > factoring turns out to be O(n^5000000) then P=NP, but I don't see
> > that causing many practical problems. *Even if it is something more
>
> I thought that it wasn't known exactly what complexity class integer
> factorization is in, and so a polynomial time algorithm for it would not
> imply P=NP. *Have I missed a development here, or am I misremembering?

That is the stated position but I found it odd, so when I had
indications that integer factorization had a simple solution I went to
TSP, to see.

And the same technique of additional degrees of freedom gave me an
algorithm.

And I saw the same denial I'd seen with all my research, from prime
counting to factoring, so I discounted it.

I now believe that class issues have to do with some people deciding
ahead of time what they wish to believe and then daring the world to
do different.

We are now watching a changing of the world order which I have feared
and the denial is still there.

If you people succeed the United States will no longer be the dominant
country in the world.

I am still hopeful that we can at least avoid a nuclear event.

But I'm running out of ideas for how to stop you.

But you are confident to the end, and as convincing as always, and so
many people seem ready to follow you over the cliff, even now as they
lose their houses and livelihoods, as in the past that is what worked.

But it's a new world.


James Harris

In article
<4ad654d9-eeec-4220-9d11-0113f3aab016@v1g2000pra.googlegroups.com>,
JSH <jstevh@gmail.com> wrote:
> We are now watching a changing of the world order which I have feared
> and the denial is still there.
>
> If you people succeed the United States will no longer be the dominant
> country in the world.
>
> I am still hopeful that we can at least avoid a nuclear event.
>
> But I'm running out of ideas for how to stop you.

What about The Hammer?

--
--Tim Smith

JSH <jstevh@gmail.com> writes:


[...]

> If you people succeed the United States will no longer be the dominant
> country in the world.
>
> I am still hopeful that we can at least avoid a nuclear event.
>
> But I'm running out of ideas for how to stop you.

Well, no wonder. Your heart's probably not in it.

Used to be that the threat we faced was the end of humanity itself.
Now, it's just a power struggle between nations. How dull and
parochial.

Frankly, it must be a letdown. Back in the day, you faced a way
bigger and more ominous threat. With space aliens, too.

--
One these mornings gonna wake | Ain't nobody's doggone business how
up crazy, | my baby treats me,
Gonna grab my gun, kill my baby. | Nobody's business but mine.
Nobody's business but mine. | -- Mississippi John Hurt

On Aug 24, 5:59*am, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
> JSH <jst...@gmail.com> writes:
>
> [...]
>
> > If you people succeed the United States will no longer be the dominant
> > country in the world.
>
> > I am still hopeful that we can at least avoid a nuclear event.
>
> > But I'm running out of ideas for how to stop you.
>
> Well, no wonder. *Your heart's probably not in it.
>
> Used to be that the threat we faced was the end of humanity itself.
> Now, it's just a power struggle between nations. *How dull and
> parochial. *
>
> Frankly, it must be a letdown. *Back in the day, you faced a way
> bigger and more ominous threat. *With space aliens, too.

I've been solving problems.

Thankfully, the rest of the world is not quite as out of it as people
in the United States and Britain.

So the threats have diminished in size.

But now I'm fighting the smaller task of saving my own country, and it
is getting to be a more desperate one, with time running out.


James Harris

JSH <jstevh@gmail.com> writes:

> On Aug 24, 5:59*am, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
>> JSH <jst...@gmail.com> writes:
>>
>> [...]
>>
>> > If you people succeed the United States will no longer be the dominant
>> > country in the world.
>>
>> > I am still hopeful that we can at least avoid a nuclear event.
>>
>> > But I'm running out of ideas for how to stop you.
>>
>> Well, no wonder. *Your heart's probably not in it.
>>
>> Used to be that the threat we faced was the end of humanity itself.
>> Now, it's just a power struggle between nations. *How dull and
>> parochial. *
>>
>> Frankly, it must be a letdown. *Back in the day, you faced a way
>> bigger and more ominous threat. *With space aliens, too.
>
> I've been solving problems.
>
> Thankfully, the rest of the world is not quite as out of it as people
> in the United States and Britain.

What did the rest of the world do to fix things?

> So the threats have diminished in size.
>
> But now I'm fighting the smaller task of saving my own country, and it
> is getting to be a more desperate one, with time running out.

Have you considered a collaboration with Mehran Basti (in sci.math)?
Together, I bet you two could solve most everything in world affairs.

--
Jesse F. Hughes
"All Chinese are Confucianists when successful, and Taoists when they
are failures."
-- Lin Yutang, /My Country and My People/

In article <reply_in_group-89161E.16524523082008@news.supernews.com>,
Tim Smith <reply_in_group@mouse-potato.com> wrote:
>In article <g8pn1r$jk$1@xenon.Stanford.EDU>,
> amorgan@xenon.Stanford.EDU (Alan Morgan) wrote:
>
>> Depends on the key size and on the nature of the algorithm. If
>> factoring turns out to be O(n^5000000) then P=NP, but I don't see
>> that causing many practical problems. Even if it is something more
>
>I thought that it wasn't known exactly what complexity class integer
>factorization is in, and so a polynomial time algorithm for it would not
>imply P=NP. Have I missed a development here, or am I misremembering?

No, I'm just wrong :-(

Alan
--
Defendit numerus

Jesse F. Hughes schrieb:
> JSH <jstevh@gmail.com> writes:
>
>> On Aug 24, 5:59 am, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
>>> JSH <jst...@gmail.com> writes:
>>>
>>> [...]
>>>
>>>> If you people succeed the United States will no longer be the dominant
>>>> country in the world.
>>>> I am still hopeful that we can at least avoid a nuclear event.
>>>> But I'm running out of ideas for how to stop you.
>>> Well, no wonder. Your heart's probably not in it.
>>>
>>> Used to be that the threat we faced was the end of humanity itself.
>>> Now, it's just a power struggle between nations. How dull and
>>> parochial.
>>>
>>> Frankly, it must be a letdown. Back in the day, you faced a way
>>> bigger and more ominous threat. With space aliens, too.
>> I've been solving problems.
>>
>> Thankfully, the rest of the world is not quite as out of it as people
>> in the United States and Britain.
>
> What did the rest of the world do to fix things?
>
>> So the threats have diminished in size.
>>
>> But now I'm fighting the smaller task of saving my own country, and it
>> is getting to be a more desperate one, with time running out.
>
> Have you considered a collaboration with Mehran Basti (in sci.math)?
> Together, I bet you two could solve most everything in world affairs.
>

I think Xah Lee would be the best fitting partner for him.
Though I doubt Xah Lee would be into it. Xah Lee's can start a flame by
just posting a single well written bollocks. JSH has to feed his
bullshit steadily so the thread grows.



OMG you were talking here about the morale of some P=NP algorithm all
that are still in their right mind doubt to work.

JSH still lacks of any Mathematical proof for his algo to work ..
he lacks even describing his algorithm in a way that makes it for others
understandable. He is not even able to hack together a program
demonstrating his algorithm ... which should be less than 2 hours of work.


I hate it to say but I am no longer open minded about the stuff JSH
proposes and no longer willing to read any more bullocks here.
The only reason I keep watching this thread currently is giving out
Links to diffrent people on my University to have a good laugh.

I am sorry for the harsh words but who ever is unable to write down an
algorithm in a way others can understand it.
Or write a program to describe the algorithm.
Or write a proove for it working (which would need a definition).

Shows with this a mathematical ineptness that gives about the same
improbability that the algorithm works as the claim it solves P=NP
question. (Both together ...)

Please couldn't this thread go on in some politics / alt.religion group.
It has nothing to do with java. And the comp.science part (another group
that exists, though would have less patience with JSH) is less and less
credible. (From if the algo works to what would happen if the algo would
be released to the public, wow.)

Christian