Can NP-Intermediate Exist if P = NP?

I understand that Ludner's theorem is basically like this:

P! = NP means that there are many NPIs where NPI is not in P and NPI is not NP-complete

What happens to this theorem if we assume that P = NP and not P! = NP? We know that if NP Intermediate does not exist, then P = NP. But can an intermediate NP exist if P = NP?

+3
source share
5 answers

An NPI should imply that it is in an NP, but that it is not NP-complete.

P = NP, P NP NP-, (βˆ… Ξ£ * NP-, - / . , P, .)

NP NP-, NPI .

+3

NPI: NPI NP ( P). , P = NP, , P = NP, NPI .

+3

P = NP, NPI , , NP, NP P , , " P" NPI . , NPI .

+2

, P = NP.

$A\rightarrow B $ $not (A) $... .

, $P = NP $ $NP $ Cook $NP-complete $... , , (, , ), , , .... , . .

- $P = NP $.

+1

. P = np class Partition (object): def init (self): self._Partition = {'db': {}, 'seek': 0, 'for': 2, 'tap': 11} i1 (0, 2): i2 (2, 4): i3 (4, 6): i4 (6, 8): i5 (8, 10): i6 (10, 12): self._Partition ['db'] [len (self._Partition ['db'])] = {'address': [i1, i2, i3, i4, i5, i6], 'data': []}

def append(self,data):
    self._Partition['db'][self._Partition['seek'] % len(self._Partition['db'])]['data'].append(data)
    self._Partition['seek'] += 1
    return self._Partition['db'][self._Partition['seek'] -1 % len(self._Partition['db'])]['address']

def address(self,data):
    for values in self._Partition['db'].values():
        if data in values['data']:
            return values['address']

def addressTOzero(self, address):
    _address = []
    index = 0
    for id in address:
        for i in range(self._Partition['tap']):
            if (id - index) == i:
                _address.append(i)
        index += self._Partition['for']

    return _address

def zeroTOaddress(self, address):
    _address = []
    index = 0
    for id in address:
        _address.append(index + id)
        index += self._Partition['for']
    return _address

def extrack(self,address):
    data = []
    for values in self._Partition['db'].values():
        if not False in [id in values['address'] for id in address]:
            data += values['data']
    return data

Partition = Partition() print ('all address', [Partition.append(data = x) x (64)]) print ('0', Partition.extrack(address = Partition.zeroTOaddress(address = [0 ]))) print ('1', Partition.extrack(address = Partition.zeroTOaddress(address = [1]))) print() print ('data to address int', Partition.address(data = 30)) print ('data to address 0 1', Partition.addressTOzero(address = Partition.address(30))) print() print ('address to data', Partition.extrack(address = Partition.zeroTOaddress(address = [0, 1, 1, 1, 1,0]))) print ('address to data', Partition.extrack ( = Partition.zeroTOaddress ( = [0, 1, 1, 1, 1])))

0

Source: https://habr.com/ru/post/1740695/


All Articles