Proving that P <= NP

As most people know, P = NP is unproven and seems unlikely. The proof will prove that P <= NP and NP <= P. However, only one of them is complex.

P <= NP is almost by definition true. In fact, this is the only way I know how to argue that P <= NP. It is just intuitive. How would you prove that P <= NP?

+4
source share
5 answers

I think you basically answered your question in the comments: a problem that satisfies the definition Palso satisfies the definition NP.

To quote wikipedia:

P [ NP] (For, P, . , , - .)

, , - - ; , P , , NP.

() . . wikipedia NP.

, , , , , . " " .

+12

NP [ ]. ( *)

P [ ]. ( )

. ()

, P [ ].

, P NP. , P & sube; NP.


* NP:

NP , .

.

+14

, P . , .

+1

, (NP) , P .

, NP , P P Time. () .

0

.

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


All Articles