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 20:04 +0100
Organization	A noiseless patient Spider
Message-ID	<87r1fh3psf.fsf@bsb.me.uk> (permalink)
References	(13 earlier) <17d77cd8-cbc8-4932-be1d-f909c3297c6an@googlegroups.com> <bcf74a9c-7ad9-4231-b906-4131c8cd2ce4n@googlegroups.com> <f543e865-41eb-4935-a30b-b71b21357fa0n@googlegroups.com> <cf50372b-db6f-4cde-9714-208317f54ec8n@googlegroups.com> <0d832976-8f5c-4569-871c-93ae9fe279e8n@googlegroups.com>

Show all headers | View raw

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

> On Thursday, 29 July 2021 at 14:24:10 UTC+1, pehou...@gmail.com wrote:
>> they had a track 1 for correct solvers but 
>> they accepted boneheaded approzimations 
>> as better than "no answer in allotted time". 
>> now they refuse to respond to email 
>> without any details of how bob did 
>> for three weeks of my trying 
>> 
> It seems you've got a legitimate complaint. If track 1 is for exact solvers,
> but if the program runs out of time it is expected to submit an approximate
> result, which bob doesn't do, it would seem to be rather unfair. However
> the organisers may have their reasons.

It's a bit odd.  According to the explanatory documents, the score is
simply the number of acceptable solutions over all the competition
instances, but an acceptable solution can be approximate.  Thus it would
seem that a solver that gets 10 problems exactly right won't score
better than one that gets 10 problems approximately right, and will
actually loose to a solver that get not exactly right but gets 11
approximations in the right range.

Unless this is not the scoring used for all tracks, I'm not sure how
track 1 can be described as "for exact solvers only".  Maybe the
permission for a solution to be within some error bound is not applied
for track 1 solvers.

-- 
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