Re: How about helping optimization in language?

From	Paul Rubin <no.email@nospam.invalid>
Newsgroups	comp.lang.forth
Subject	Re: How about helping optimization in language?
References	(10 earlier) <jlv01a$evd$1@online.de> <7xiph86tbe.fsf@ruckus.brouhaha.com> <2012Apr10.113955@mips.complang.tuwien.ac.at> <7xty0rq4jl.fsf@ruckus.brouhaha.com> <jm27l5$5ku$1@online.de>
Date	2012-04-10 21:18 -0700
Message-ID	<7xvcl652ay.fsf@ruckus.brouhaha.com> (permalink)
Organization	Nightsong/Fort GNOX

Show all headers | View raw

Bernd Paysan <bernd.paysan@gmx.de> writes:
> Well, it's sloppy wording, but what I mean is "in and only in NP, under 
> the assumption that P!=NP".  Given that P!=NP has no proof, it is a bit 
> difficult to correctly speak about these things, but that doesn't really 
> matter.  You know what I mean, and that's what communication is about.

OK, you wanted a problem in NP but outside of P.  Integer factoring (IF)
is generally believed to be in that class, according to what I've heard.
Specifically I think IF is generally believed to be NP-intermediate
(outside P but not NP-hard).  Ladner's theorem says that such problems
necessarily exist, if P!=NP.  I remember hearing that any public-key
primitive might necessarily be like that (i.e. not NP-hard), but I don't
know the reasoning.  I know IF is believed not NP-hard partly because
it's in both NP and co-NP.

> In general, all crypto algorithms use algorithms which are presumed to 
> be NP-hard, and no easy to solve subset exists. 

I don't have the impression crypto primitive designers really consider
NP-hardness much.  It makes no sense for something like AES, which works
on a fixed number of bits, so it can be solved in constant time (for an
impractically large constant).  I don't think there are any strong
complexity results (such as NP-completeness) for elliptic curve discrete
logs, just the absence of known sub-exponential algorithms.  The US
government (i.e. the NSA) seems to prefer ECC over RSA, so maybe they
know something we don't.  The commercial world doesn't seem worried
about RSA though, at least per guys I talked to as of a few years ago.

Also, as described in Impagliazzo's article that I linked, we could be
in a world where P!=NP and yet there are no actual hard public key
primitives, or maybe not even any hard symmetric primitives (even if the
worst case of a problem is exponentially hard, the average case might
always be easy).  Crypto theorists seem to just assume certain
primitives are hard to break, and use that assumption to prove
difficulty results about various combinations of the primitives.

>  The Knapsack based cryptosystems are an example...
> http://math.univ-angers.fr/~evain/npComplet.pdf

That paper is interesting, thanks.  Knapsack cryptosystems are the only
examples I knew of that tried to use an NP-complete problem, and at
least in their early history they failed miserably: see

   http://cr.yp.to/bib/1988/diffie.pdf

p. 6 of the pdf (p. 565 of the article), "Fall of the knapsacks".
Amusingly the knapsack system described in the paper reduces to factoring.

In principle, one could use problems outside of NP.  I remember seeing
something about a hypothetical cryptosystem based on the word problem
for finitely presented groups, which is undecidable.  I guess that means
the key length could be arbitrary.  The encryption and decryption time
would depend on the key length, and the attacker would not know whether
the key was 100 bits, or a million bits, or a billion bits, or if he had
been slipped an invalid ciphertext with no corresponding plaintext.
Even with an arbitrarily fast computer, he would never know when to stop
searching.

But, this all gets rather tangential.  The idea of that factoring story
is just that there's inherent complexity lurking even in some very
simply stated problems, because of the infinitely complex structure of
the natural numbers.

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-01 22:48 -0700
  Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-02 04:41 -0500
    Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-02 17:40 -0700
      Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-02 15:35 -1000
        Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-02 19:25 -0700
          Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-02 20:45 -1000
          Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-03 00:51 -0700
            Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-02 22:17 -1000
              Re: How about helping optimization in language? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-03 02:32 -0700
            Re: How about helping optimization in language? mhx@iae.nl (Marcel Hendrix) - 2012-04-03 20:22 +0200
              Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 11:53 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 09:10 -1000
              Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-03 14:16 -0700
                Re: How about helping optimization in language? mhx@iae.nl (Marcel Hendrix) - 2012-04-05 21:27 +0200
            Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-03 22:27 +0200
              Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 10:45 -1000
                Re: How about helping optimization in language? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-04 10:34 +0000
          Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-03 00:43 -0700
      Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-03 03:59 -0500
        Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 20:34 -0700
          Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-04 05:32 -0500
            Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-07 22:15 -0700
              Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-08 04:55 -0500
              Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-08 15:51 +0000
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-08 11:34 -0500
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 13:11 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-08 23:40 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 15:14 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-09 09:37 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:05 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 10:32 +0000
              Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-08 23:18 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 20:51 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-08 19:09 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 21:05 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 21:57 -1000
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-09 17:42 +0200
                Re: How about helping optimization in language? jacko <jackokring@gmail.com> - 2012-04-09 09:34 -0700
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 22:37 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 09:39 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 03:12 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-10 23:11 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 21:18 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-11 10:00 +0000
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-10 22:12 +0200
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-10 16:24 -0500
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 08:34 +0000
                Re: How about helping optimization in language? John Passaniti <john.passaniti@gmail.com> - 2012-04-09 10:09 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-09 21:21 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:02 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 16:44 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:00 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 17:27 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:49 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 18:12 -1000
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 10:24 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 03:40 -0700
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-10 04:39 -0500
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 03:05 -0700
                Re: How about helping optimization in language? Coos Haak <chforth@hccnet.nl> - 2012-04-10 18:13 +0200
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-10 12:02 -0500
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 14:36 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 23:01 -0700
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-11 00:51 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-10 22:18 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-11 02:45 -0700
                Re: How about helping optimization in language? "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2012-04-11 19:47 +0100
                Complexity (was: How about helping optimization in language?) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-09 08:52 +0000
                Re: Complexity (was: How about helping optimization in language?) Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-09 03:01 -0700
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-09 10:17 -0700
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:33 -1000
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:43 -1000
                Re: Complexity (was: How about helping optimization in language?) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 07:31 +0000
                Re: Complexity (was: How about helping optimization in language?) Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-09 17:08 +0200
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:21 -1000
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:30 -0700
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 22:19 -1000
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-10 01:48 -0700
                Re: Complexity Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-10 01:28 -0700
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 22:48 -1000
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-10 01:51 -0700
                Re: Complexity Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-10 20:06 +0000
                Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-09 10:24 +0000
                Re: How about helping optimization in language? Nomen Nescio <nobody@dizum.com> - 2012-04-09 16:18 +0200
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-09 07:23 -0700
                Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-09 15:27 +0000
          Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-04 06:51 -0700
      Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-03 09:06 +0000
      Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-03 16:13 +0000
        Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 12:43 -0700
          Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 10:16 -1000
            Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 13:41 -0700
              Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 11:01 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 22:42 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 21:11 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 01:02 -0700
          Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-04 05:35 -0500
            Re: How about helping optimization in language? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-04 15:01 +0000
            Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-06 00:08 -0700
              Re: How about helping optimization in language? Jan Coombs <jan_2011-02@murray-microft.co.uk> - 2012-04-06 12:05 +0100
          Re: How about helping optimization in language? Alex McDonald <blog@rivadpm.com> - 2012-04-03 15:56 -0700
        Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-03 22:06 +0200
          Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 13:22 -0700
          Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-04 05:43 -0500
            Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-04 23:15 +0200
            Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 19:02 -0700
          Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-04 13:34 +0000
  Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-02 09:49 +0000
    Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-02 20:04 -0700
      Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-03 09:30 +0000
        Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 13:16 -0700
          Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-03 22:45 +0200
            Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 23:26 -0700
              Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 21:29 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 02:32 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-04 07:30 -1000
                Re: How about helping optimization in language? John Passaniti <john.passaniti@gmail.com> - 2012-04-04 08:51 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-04 10:31 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-07 21:20 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-07 19:18 -1000
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-08 15:59 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 22:12 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-08 19:42 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 23:26 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-08 20:37 -1000
                Re: How about helping optimization in language? Fritz Wuehler <fritz@spamexpire-201204.rodent.frell.theremailer.net> - 2012-04-09 23:33 +0200
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:52 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 18:42 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 15:57 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:08 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 16:29 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:53 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 17:05 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:15 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-10 21:46 +0200
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 10:42 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-11 21:26 -0700
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-12 00:24 -0700
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-12 01:55 -0700
          Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-03 22:06 +0000
            Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-04 13:20 +0000
              Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-04 21:18 +0000
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-05 15:36 +0000
                Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-05 18:32 +0000
          Re: How about helping optimization in language? kenney@cix.compulink.co.uk - 2012-04-04 04:39 -0500
            Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 02:50 -0700
          Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-03 18:07 -0700
            Re: How about helping optimization in language? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-05 11:10 +0000
              Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-05 13:21 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-05 23:26 +0200
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-05 14:49 -0700
                Re: How about helping optimization in language? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-04-06 08:58 +0100
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-06 19:07 +0200
                Re: How about helping optimization in language? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-04-07 10:07 +0100
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-07 21:18 +0200
                Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-08 07:36 -0700
                Re: How about helping optimization in language? jacko <jackokring@gmail.com> - 2012-04-08 07:56 -0700
                Re: How about helping optimization in language? jacko <jackokring@gmail.com> - 2012-04-08 07:49 -0700

csiph-web