Re: Factoring integers on a classical computer

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/18/05

  • Next message: Ajoy K Thamattoor: "Re: Factoring integers on a classical computer" 
    Date: 17 Mar 2005 15:34:13 -0800

    tchow@lsa.umich.edu wrote:
    > In article <1111088872.090754.120240@z14g2000cwz.googlegroups.com>,
    > Pubkeybreaker <Robert_silverman@raytheon.com> wrote:
    > >"Can anyone give an example of a problem in
    > >which determining whether a solution exists is easy (can be done in
    > >poly-time), but where finding the solution has been proven to
    require
    > >super-polynomial time? "
    >
    > I don't have a good example off the top of my head, but consider the
    > following near-miss. Consider the game of Hex.
    >
    > http://en.wikipedia.org/wiki/Hex_(board_game)
    >
    > A simple strategy-stealing argument shows that the first player has a
    > winning strategy. Finding the strategy, however, is an entirely
    different
    > matter...
    >

    Thank you, that's certainly a good example, even though it's near-miss.
    I claimed on previous posts (on a different thread in a joking
    argument) that mathematical theorems can never be surprising, since
    they are deductive. After thinking about the integer factoring problem,
    I take this back, as the fact that one can determine that there are
    factors without constructively calculating the factors is, what I would
    call, surprising.

    Craig

  • Next message: Ajoy K Thamattoor: "Re: Factoring integers on a classical computer"

    Relevant Pages

    • Re: Factoring integers on a classical computer
      ... > I don't have a good example off the top of my head, ... Consider the game of Hex. ... argument) that mathematical theorems can never be surprising, ...
      (sci.math)
    • Re: England - what to do with the oldies
      ... "Two Dogs" wrote in message ... but he just keeps surprising me. ... the park and in the lineout. ... I'm not so sure in a 22 man game. ...
      (rec.sport.rugby.union)
    • Re: McMisanthropes Top 25: September 20, 2009
      ... I was not surprised about the USC game, as it had "trap" written all ... More surprising was BYU, especially at home, but maybe they believed ... Sagarin has their SOS as the ... TCU -- Now the MWC's only shot at a BCS bowl. ...
      (rec.sport.football.college)
    • Re: Stalker: Clear Sky To Be Released Exclusively On Steam... according to Toms Hardware
      ... I do find it surprising that the game wasn't made with reduced details in at least these fps-critical situations to avoid stuttering (and the stuttering was really heavy. ... In EP1, there is room flooded with water, a door on the one side and a switch that opens the door on the other side. ...
      (comp.sys.ibm.pc.games.action)
    • McMisanthropes Top 25: September 20, 2009
      ... I was not surprised about the USC game, ... only play to their potential in their bowl game in most years, ... More surprising was BYU, especially at home, but maybe they ... Sagarin has their SOS as ...
      (rec.sport.football.college)