Re: Factoring integers on a classical computer

tchow_at_lsa.umich.edu
Date: 03/18/05 

Date: 18 Mar 2005 14:03:50 GMT

In article <1111102453.493559.44940@l41g2000cwc.googlegroups.com>,
Craig Feinstein <cafeinst@msn.com> wrote:
>as the fact that one can determine that there are factors without
>constructively calculating the factors is, what I would call, surprising.

A great deal of attention has been given to this "surprising" phenomenon
of "non-constructive proofs." In some situations there are proofs that
something exists without there being *any* algorithm, however inefficient,
to find it. For example, one can prove that the rank of an elliptic curve
over Q is finite, but there is no known algorithm to compute the rank. Some
people find this phenomenon so disconcerting that they declare it not only
surprising but illegal, and they reject the logical principle (the law of
the excluded middle) on which such proofs are based.

More in line with what you're talking about are situations in which there's
a proof of existence which is "constructive" in the sense that there's an
obvious brute-force algorithm to find the object of interest, but no known
*efficient* method of construction. Hex falls into that category, as does
factorization. Many proofs using the so-called "probabilistic method" of
Erdos are like this. You can find other examples in the following papers.

 http://www.math.tau.ac.il/~nogaa/PDFS/nocon.pdf
 http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf 

-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences

Relevant Pages

  • Re: Factoring integers on a classical computer
    ... >constructively calculating the factors is, what I would call, surprising. ... but there is no known algorithm to compute the rank. ... *efficient* method of construction. ... Many proofs using the so-called "probabilistic method" of ...
    (comp.theory)
  • Re: How to model decoupled hierarchies?
    ... Basically the class surface has a methode "void reconstruct( ... encapsulates the actual algorithm for reconstruction. ... The notion here of creating being the whole business logic and main purpose seems more appropriate for a particular subsystem whose subject matter was explicitly that construction. ... of) two slices), the section holds references to the slices. ...
    (comp.object)
  • Re: How to model decoupled hierarchies?
    ... My inclination would be to encapsulate that mapping algorithm in some sort of factory object that builds the entire Surface structure by "walking" the relationships of the Object in hand. ... Now one doesn't need explicit relationships between Surface elements and Object elements. ... I am guessing you only need those to abstract how the two surface structures are related during the construction of a Surface from an Object. ...
    (comp.object)
  • Re: Commonality in subset construction and LR set of items construction algorithms
    ... a hard time as seeing them as anything but one algorithm. ... The idea of LR parsing is that a handle in a sentential form, i.e. the part of the sentential form which should be reduced in canonical bottom-up parsing, can be identified by a finite state automaton---sometimes dubbed handle-finding automaton. ... happens that, for any context-free grammars, the language of terminals and nonterminals prefixes up to the point where a reduction should occur is a regular language, and can be computed from the grammar. ... Constructing a deterministic finite state automaton from this grammar to find the handles in sentential forms ends up being the same as the LR item subset construction. ...
    (comp.theory)
  • Re: Concurrency problem: Compare and swap good enough?
    ... processes need to access the same buffer ... > in a realtime operating system i.e. one process can be preempted while ... However, that particular construction is ... simple mutual exclusion algorithm. ...
    (comp.programming)