Welcome to novaBBS (click a section below) |
mail files register newsreader groups login |

Message-ID: |

Subject | Author |

ANP!=P suggests NP!=P | wij |

1 |

<06814de4-1fdd-413c-8af9-ae17c0cf81d3n@googlegroups.com>

https://www.novabbs.com/devel/article-flat.php?id=463&group=comp.lang.c%2B%2B#463

X-Received: by 2002:a37:8701:0:b0:762:407d:3837 with SMTP id j1-20020a378701000000b00762407d3837mr2492422qkd.6.1687333705218;

Wed, 21 Jun 2023 00:48:25 -0700 (PDT)

X-Received: by 2002:ad4:4bac:0:b0:62f:eb62:7afa with SMTP id

i12-20020ad44bac000000b0062feb627afamr1873350qvw.6.1687333705036; Wed, 21 Jun

2023 00:48:25 -0700 (PDT)

Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail

Newsgroups: comp.lang.c++

Date: Wed, 21 Jun 2023 00:48:24 -0700 (PDT)

Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=0Ek0TQoAAAAS0oceh95IuNV59QuIWNeN

NNTP-Posting-Host: 124.218.76.41

User-Agent: G2/1.0

MIME-Version: 1.0

Message-ID: <06814de4-1fdd-413c-8af9-ae17c0cf81d3n@googlegroups.com>

Subject: ANP!=P suggests NP!=P

From: wynii...@gmail.com (wij)

Injection-Date: Wed, 21 Jun 2023 07:48:25 +0000

Content-Type: text/plain; charset="UTF-8"

Content-Transfer-Encoding: quoted-printable

by: wij - Wed, 21 Jun 2023 07:48 UTCWed, 21 Jun 2023 00:48:25 -0700 (PDT)

X-Received: by 2002:ad4:4bac:0:b0:62f:eb62:7afa with SMTP id

i12-20020ad44bac000000b0062feb627afamr1873350qvw.6.1687333705036; Wed, 21 Jun

2023 00:48:25 -0700 (PDT)

Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail

Newsgroups: comp.lang.c++

Date: Wed, 21 Jun 2023 00:48:24 -0700 (PDT)

Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=0Ek0TQoAAAAS0oceh95IuNV59QuIWNeN

NNTP-Posting-Host: 124.218.76.41

User-Agent: G2/1.0

MIME-Version: 1.0

Message-ID: <06814de4-1fdd-413c-8af9-ae17c0cf81d3n@googlegroups.com>

Subject: ANP!=P suggests NP!=P

From: wynii...@gmail.com (wij)

Injection-Date: Wed, 21 Jun 2023 07:48:25 +0000

Content-Type: text/plain; charset="UTF-8"

Content-Transfer-Encoding: quoted-printable

ANP={q| q is an algorithmic decision problem. Let q(n) be the computing function

of q using n as the problem argument. If given additional information c,

the case that q(n)=1 can be computed in P-time.

}

Specifically, the semantics of ANP suggests that a P-time function q'(n,c) is

given (otherwise, q won't be well defined), and:

q'(n,c): S×S ->{0,1}, where S={0,1}^N.

That q'(n,c) returns 1 means q(n)=1 (0 means c is not decisive).

Therefore, q(n) can be generalized in this C-like pseudo-program when c is

necessary:

bool q(n) {

begin= get_begin(n);

end = get_end(n);

for(c=begin; c!=end; c=next(c)) {

if(q'(n,c)) return 1;

}

return 0;

}

Note that the above is attributed as generalized is because the unknown

information c has O(2^N) possibilities (worst case), each of them have to be

explicitly generated and tested. There may be doubt that one possibility of c may contain information about another case (or, can q' return any suggestive

information?). The short answer is: it does not matter because the c asked by

ANP may be a pure bit-string that each bit is independent.

ANP is defined the kind of problem that O(2^N) unknown independent possibilities

HAS TO BE FIXED to compute in P-time (worst case). This is the essence of this

proof. In applications, a specific problem in doubt may need to show it does

require c information (O(2^N) possibilities) to fit in ANP, not easy (hope I am

wrong), but this is not the problem of ANP (this part is indirectly covered by

NP and NPC theory).

----------------

Also, as posted in C/C++ group, I would like to say that program has to be

able to show it is correctly (optimally provable) written for the problem.

I.e. the application of the language may include theorem proving.

Sub-goals like expressiveness, 'cleanness' make correctness proving difficult

(esp. error handling is considered)... If something is good, something has to

be considered not good. Every new feature makes others less reusable.

1 |

clearnet tor