Re: revised relativization theorem: P=NP for small N, P!=NP for large N

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.theory
Subject	Re: revised relativization theorem: P=NP for small N, P!=NP for large N
Date	2021-07-29 15:56 +0100
Organization	A noiseless patient Spider
Message-ID	<878s1p5ft5.fsf@bsb.me.uk> (permalink)
References	(14 earlier) <875ywu8bdq.fsf@bsb.me.uk> <db8b0dc8-1657-454d-a48f-fe4dc4c267c4n@googlegroups.com> <17d77cd8-cbc8-4932-be1d-f909c3297c6an@googlegroups.com> <bcf74a9c-7ad9-4231-b906-4131c8cd2ce4n@googlegroups.com> <f543e865-41eb-4935-a30b-b71b21357fa0n@googlegroups.com>

Show all headers | View raw

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Thursday, 29 July 2021 at 01:41:29 UTC+1, pehou...@gmail.com wrote:
>> ben, is this clear? 
>> 
>> in track 1 the correctness track 
>> approximation is senseless is what i am saying 
>> 
>> in track 2 the incorrectness track 
>> approximation is fine
>>
> From what I understand, bob creates an exact solution to the problem
> whilst the competition specifies an order of magnitude estimate.

I've gone to have a look...  The competition has three tracks.  Track
one is for exact solvers and the other two allow either exact or
approximate solvers but exact solvers receive what they call a
"performance bias".

All solvers must output the base 10 log of the result, but the format
allows for an exact count as well.

> It would be astonishing if bob also ran in similar time or was capable of
> tackling the same size of problem, whilst producing an exact answer whilst
> the competitors produced only approximations. So either this is the wrong
> competition for bob, or there should be a separate track for exact solvers.
> Or, this being computer science and not the Olympics, you can say that
> you entered bob without any expectation that it would do well, to demonstrate
> an exact solver. I'd suggest maybe the third option is the most dignified one.

-- 
Ben.

Thread

revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-07 18:19 -0700
  Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-08 02:44 -0700
    Re: revised relativization theorem: P=NP for small N, P!=NP for large N DV <xlt.pjw@gmail.com> - 2021-07-08 05:37 -0700
      Re: revised relativization theorem: P=NP for small N, P!=NP for large N Jeff Barnett <jbb@notatt.com> - 2021-07-08 14:21 -0600
        Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-14 07:28 -0700
          Re: revised relativization theorem: P=NP for small N, P!=NP for large N DV <xlt.pjw@gmail.com> - 2021-07-14 14:28 -0700
            Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-15 12:51 -0700
              Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-18 03:45 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N DV <xlt.pjw@gmail.com> - 2021-07-18 06:48 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-18 14:28 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-26 04:45 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-26 14:35 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 00:35 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 02:40 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-28 17:27 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 11:50 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-28 20:52 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 15:53 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 16:58 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 17:41 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-29 01:45 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 20:07 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-28 20:27 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-29 14:59 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-29 02:27 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 06:24 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-29 07:50 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Jeff Barnett <jbb@notatt.com> - 2021-07-29 11:44 -0600
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 11:59 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Jeff Barnett <jbb@notatt.com> - 2021-07-29 13:23 -0600
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-29 20:04 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-29 15:56 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 11:53 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-29 20:12 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 13:12 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-29 23:18 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 15:36 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 16:38 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 00:59 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 17:05 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 01:19 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 17:27 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 02:22 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 19:16 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Jeff Barnett <jbb@notatt.com> - 2021-07-29 22:25 -0600
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 00:35 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 10:53 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 05:19 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 14:22 +0100
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 07:16 -0700
                Re: revised relativization theorem: P=NP for small N, P!=NP for large N Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 15:22 +0100

csiph-web