Solution of NP problem in linear time using exponential memory
Zbyszek Płotnicki
Istnieje 2^(2^k) różnych funkcji logicznych których można użyć.
Złożenie dowolnych z tych dwóch funkcji jest którąś z tych funkcji i
dalej idąc dowolne wyrażenie jest równoważne którejś z tych funkcji.
Tworzymy tablicę
k| 1 2 3 ....... 2^(2^k)
1| aa ab ac ad ....
2| ba bb bc ....
3| ca ...
.| ...
.|
.|...
2^(2^k)|...............
Gdzie każda funkcja 'xy' nalezy do zbioru fi, i = 1, 2, ... 2^(2^k)
Dla każdej funkcji mamy listę L0 takich parametrów, że wynik jej jest
0.
Dla każdej funkcji mamy listę L1 takich parametrów, że wynik jej jest
1.
Używając tej tablicy zamieniamy w wyrażeniu każde podwyrażenie na
którąś z funkcji i tak postępujemy do zredukowania wyrażenia do jednej
funkcji w każdym kroku skracając długość wyrażenia o 1. W związku z
tym, że w dowolnym wyrażeniu o długości n jest O(n) funkcji plus
maksymalnie O(n) nawiasowań, obliczamy funkcję w czasie O(n).
Ostatecznie zaglądamy do listy L1 dla określonej funkcji i listujemy
wszystkie wartości jej parametrów dla których jest ona spełniona albo
tylko pierwszy zestaw. Robimy to w czasie O(k)
Ostatecznie zaglądamy do listy L0 dla określonej funkcji i listujemy
wszystkie wartości jej parametrów dla których nie jest ona spełniona
albo tylko pierwszy zestaw. Robimy to w czasie O(k)
Jest to rozwiązanie problemu w czasie O(n+k), liniowym w zależności od
MAX(wielkość danych, liczba symboli)
Zatem jest to rozwiązanie problemu NP-trudnego w czasie liniowym przy
użyciu wykładniczej ilości pamięci.
Wynika z tego, że każdy problem NP możemy rozwiązać w czasie
wielomianowym przy użyciu wykładniczej ilości pamięci.
CND.
Zbigniew Płotnicki
Zbyszek Płotnicki
zamieniamy każde podwyrazenie na funkcję tautologiczna z nim, aż do
przeksztalcenia calosci wyrazenia w pojedyńczą funkcję tautologiczną,
po czym następuje odczyt wartosci symboli, dla ktorych jest ona rowna
1, albo 0. Jest to możliwe ponieważ każde wyrażenie logiczne jest
równoważne którejś z funkcji ze zbioru 1 .. 2^(2^k) dla k symboli.
On 10 Lis, 17:06, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
Zbyszek Płotnicki
postaci OP_XXXX mozna obliczyć w czasie O(1) tautologie dla wyrażenia,
czyli znalezc funckje tautoliczną dla niego:
(a and b) or (a or b)
or = 0111
----
00|0
01|1
10|1
11|1
and = 0001
----
00|0
01|0
10|0
11|1
or(and(a, b)), (or(a,b)) = and(0111, 0001) = (0,0) -> 0, (1,0) -> 0,
(1,0)-> 0, (1,1)->1 = 0001
(a and b) or (a or b)
a b
-------------
0 0 | (0 and 0) or (0 or 0) = 0
0 1 | (0 and 1) or (0 or 1) = 0
1 0 | (1 and 0) or (1 or 0) = 0
1 1 | (1 and 1) or (1 or 1) = 1
Wynika z tego, że na maszynie, która realizuje wszystkie funkcje
logiczne k - argumentowe w jednostkowym czasie nie potrzeba żadnej
pamięci, żeby obliczyć tautologie dla dowolnego wyrażenia w czasie O
(n*k).
Czyli na PCcie można wyliczyć bez korzystania z pamieci wyrażenia
logiczne wykorzystujace binarne operacje.
CND.
Zbigniew Płotnicki
On 11 Lis, 07:48, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
Zbyszek Płotnicki
funkcji i można rozwiązać problem w czasie O(k), czyli dla maszyny
która w jednej jednostce zapsiuje funkcje jest ono wyliczalne w czasie
O(1).
Zbigniew Płotnicki
On 11 Lis, 09:57, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
Zbyszek Płotnicki
dla dowolnego zdania poprzez dowolne skracanie i dowolne rozwijanie.
On 11 Lis, 10:08, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
Zbyszek Płotnicki
funkcję wynika z tego, że istnieje jednoznaczne przyporządkowanie
wszystkich możliwych k-tek argumentów do tablicy wyników o wielkości
2^k, a więc każde złożenie dwóch i wielu funkcji także ma funkcję
tautologiczną z nim. i tak aż do uzyskania funkcji tautologicznej dla
całego wyrażenia.
On 11 Lis, 11:42, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > > Zatem jest to rozwiązanie problemuNP-trudnego w czasie liniowym przy
> > > > > użyciu wykładniczej ilości pamięci.
>
> > > > > Wynika z tego, że każdy problemNPmożemy rozwiązać w czasie
Zbyszek Płotnicki
symbol 'a' na funkcję select(a), czyli:
ab|select_a(a,b)
-------
00|0
01|0
10|1
11|1
-----------
ab| a and b
---------
00|0
01|0
10|0
11|1
nastepnie wykorzystujac funkcje or
xy|or
---------
00|0
01|1
10|1
11|1
obliczamy tautologie dla calego wyrazenia:
or(and(a,b), select_a(a,b)) = or(0001, 0011) = 0011, ktora przyjmuje
wartosci 1 dla par argumentow : 01, 10, 11
ab|(a and b) or a
---------------
00|0
01|0
10|1
11|1
Zbigniew Płotnicki
On 11 Lis, 12:34, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
Zbyszek Płotnicki
table : [Func_i][Arg1][Arg2]... [Argk] -> Func_r,
gdzie Func_i, Arg1, ... , Argk, Func_r należą do zbioru funkcji k
argumentowych.
Zbigniew Płotnicki
On 11 Lis, 13:14, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
Zbyszek Płotnicki
Proszę o potwierdzenie odbioru.
Tu jest link do mojego wątku na ten temat, jednak zawiera błędy, które
skorygowałem poniżej w treści e-maila.
http://groups.google.pl/group/sci.math.num-analysis/browse_thread/thread/24f2970105d00a62?hl=pl#
Mamy problem spełnialności formuły logicznej o k różnych symbolach.
Istnieje 2^(2^k) różnych funkcji logicznych których można użyć.
Złożenie dowolnych z tych funkcji jest którąś z tych funkcji i
dalej idąc dowolne wyrażenie jest równoważne którejś z tych funkcji.
Używamy tablicy o wykładniczej złożoności pamięciowej:
table : [Func_i][Arg1][Arg2]... [Argk] -> Func_r,
gdzie Func_i, Arg1, ... , Argk, Func_r należą do zbioru funkcji k
argumentowych.
Oprócz tego:
Dla każdej funkcji mamy listę L0 takich parametrów, że wynik jej jest
0.
Dla każdej funkcji mamy listę L1 takich parametrów, że wynik jej jest
1.
Używając tej tablicy (table) zamieniamy w wyrażeniu każde podwyrażenie
na
którąś z funkcji i tak postępujemy do zredukowania wyrażenia do
jednej
funkcji w każdym kroku skracając długość wyrażenia o 1. W związku z
tym, że w dowolnym wyrażeniu o długości n jest O(n) funkcji plus
maksymalnie O(n) nawiasowań, obliczamy funkcję w czasie O(n).
Ostatecznie zaglądamy do listy L1 dla określonej funkcji i listujemy
wszystkie wartości jej parametrów dla których jest ona spełniona albo
tylko pierwszy zestaw. Robimy to w czasie O(k)
Ostatecznie zaglądamy do listy L0 dla określonej funkcji i listujemy
wszystkie wartości jej parametrów dla których nie jest ona spełniona
albo tylko pierwszy zestaw. Robimy to w czasie O(k)
Jest to rozwiązanie problemu w czasie O(n+k), albo jeśli jesteśmy
zmuszeni dla każdego atomu rozwijać funkcję do select_k(a1,..ak), to
złożoność jest O(n*k), czyli jest pomiędzy tymi dwoma wartościami,
czyli jest to złożoność wielomianowa w zależności
od wielkość danych i liczby symboli.
Zatem jest to rozwiązanie problemu NP-trudnego w czasie wielomianowym
przy
użyciu wykładniczej ilości pamięci.
Wynika z tego, że każdy problem NP możemy rozwiązać w czasie
wielomianowym przy użyciu wykładniczej ilości pamięci.
CND.
--------------------------------------------------
Żeby było jasne, jak to dziala:
zamieniamy każde podwyrazenie na funkcję tautologiczna z nim, aż do
przeksztalcenia calosci wyrazenia w pojedyńczą funkcję tautologiczną,
po czym następuje odczyt wartosci symboli, dla ktorych jest ona rowna
1, albo 0. Jest to możliwe ponieważ każde wyrażenie logiczne jest
równoważne którejś z funkcji ze zbioru 1 .. 2^(2^k) dla k symboli.
------------------------
Oto jak na maszynie która ma wszystkie binarne operacje logiczne w
postaci OP_XXXX mozna obliczyć w czasie O(1) tautologie dla
jednokrotnie złożonego wyrażenia,
logiczne wykorzystujace binarne operacje i nie potrzeba bedzie pamieci
na tablice do log2(max_int_bits_count) różnych symboli = np.: log2(64)
= 6 roznych symboli.
------------------------------------------------------------------
Jeśli wyrażenie nie zawiera potwórzeń symboli to odpowiada jednej z
funkcji i można rozwiązać problem w czasie O(k), czyli dla maszyny
która w jednej jednostce zapisuje funkcje jest ono wyliczalne w
czasie
O(1).
------------------------------------------------------------------
W podany przeze mnie sposób można znależć wszystkie możliwe
tautologie
dla dowolnego zdania poprzez dowolne skracanie i dowolne rozwijanie.
------------------------------------------------------------------
To, że każde wyrażenie logiczne na k symbolach ma tautologiczną
funkcję wynika z tego, że istnieje jednoznaczne przyporządkowanie
wszystkich możliwych k-tek argumentów do tablicy wyników o wielkości
2^k, a więc każde złożenie dwóch i wielu funkcji także ma funkcję
tautologiczną z nim. i tak aż do uzyskania funkcji tautologicznej dla
całego wyrażenia.
------------------------------------------------------------------
Oczywiście, jeśli mamy np.: (a and b) or a, to zamieniamy pojedynczy
symbol 'a' na funkcję select_a, czyli:
------------------------------------------------------------------
Zbigniew Płotnicki
On 11 Lis, 15:33, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> Żeby pomóc zrozumieć jak mają wygladac tablice dla k symboli:
>
> table : [Func_i][Arg1][Arg2]... [Argk] -> Func_r,
>
> gdzie Func_i, Arg1, ... , Argk, Func_r należą do zbioru funkcji k
> argumentowych.
>
> Zbigniew Płotnicki
>
> On 11 Lis, 13:14, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
> wrote:
>
>
>
> > Oczywiście, jeśli mamynp.: (a and b) or a, to zamieniamy pojedynczy
Zbyszek Płotnicki
nastepuje skrócenie za każdym razem z k*2^k do 2^k, a gdybysmy
pozbywali się za każdym razem tylko 2^k z długości ciągu to złożoność
byłaby wielomianowa, bo takich operacji byłoby (k*n)/2^k, co dałoby
(k*n)/2^k * 2^k = k * n. Czyli w każdym kroku pozbywamy się 2^k *
(k-1) z dlugosci ciągu, co dowodzi tego, że złożoność jest n*k.
Ponieważ liczba wszystkich operacji będzie conajwyzej : O(2^k * (k*n /
2^k)).
I nie jest potrzebna żadna tablica poza tablicami wynikow funkcji dla
okreslonych argumentow, bo zamieniamy w czasie k*k^2 korzystajac z
tych tablic tak jak pokazalem wyzej na ciąg k^2, skracając tak jak
napisalem wyżej o (k-1)*2^k, czyli złożoność O(n*k) bez użycia żadnych
tablic.
Zbigniew Płotnicki
On 12 Lis, 19:33, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> Skorygowana tresc:
>
> Proszę o potwierdzenie odbioru.
>
> Tu jest link do mojego wątku na ten temat, jednak zawiera błędy, które
> skorygowałem poniżej w treści e-maila.
>
> http://groups.google.pl/group/sci.math.num-analysis/browse_thread/thr...
> Zatem jest to rozwiązanie problemuNP-trudnego w czasie wielomianowym
> przy
> użyciu wykładniczej ilości pamięci.
>
> Wynika z tego, że każdy problemNPmożemy rozwiązać w czasie
> wielomianowym przy użyciu wykładniczej ilości pamięci.
>
> CND.
>
> na tablice do log2(max_int_bits_count) różnych symboli =np.: log2(64)
> = 6 roznych symboli.
> ------------------------------------------------------------------
> Jeśli wyrażenie nie zawiera potwórzeń symboli to odpowiada jednej z
> funkcji i można rozwiązać problem w czasie O(k), czyli dla maszyny
> która w jednej jednostce zapisuje funkcje jest ono wyliczalne w
> czasie
> O(1).
> ------------------------------------------------------------------
> W podany przeze mnie sposób można znależć wszystkie możliwe
> tautologie
> dla dowolnego zdania poprzez dowolne skracanie i dowolne rozwijanie.
> ------------------------------------------------------------------
> To, że każde wyrażenie logiczne na k symbolach ma tautologiczną
> funkcję wynika z tego, że istnieje jednoznaczne przyporządkowanie
> wszystkich możliwych k-tek argumentów do tablicy wyników o wielkości
> 2^k, a więc każde złożenie dwóch i wielu funkcji także ma funkcję
> tautologiczną z nim. i tak aż do uzyskania funkcji tautologicznej dla
> całego wyrażenia.
> ------------------------------------------------------------------
> > > > > > > > > dalej idąc dowolne wyrażenie jest równoważne którejś z tych funkcji....
>
> więcej >>
Zbyszek Płotnicki
czasie conajwyżej O(n*k). Co udowadnia, że jest to algorytm
wielomianowy w zależności od wielkości danych wejściowych.
On 13 Lis, 12:24, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > > > > > logiczne k - argumentowe w jednostkowym czasie nie potrzeba żadnej...
>
> więcej >>
Zbyszek Płotnicki
formuł użytych d razy, wtedy w postaci binarnej ciąg ten wymaga:
O(b*2^log2(a) + d*2^log2(c)) -> n bitów danych wejściowych i złożoność
algorytmu jest taka sama.
Zbigniew Płotnicki
On 13 Lis, 12:44, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > > > > > > 01|1...
>
> więcej >>
Zbyszek Płotnicki
zatem jest mniejsza od O(n^2). Gdy k zbliża się do n to mamy coraz
mniej przekształceń, czyli złożoność zbliża się do O(n).
Co więcej nie trzeba żadnych tablic dla wszystkich funkcji k-
argumentowych, bo są to liczby naturalne po pierwsze podane w ciagu
wejsciowym gdy sa uzyte, po drugie wyliczone przy kazdym skroceniu ze
zwyklej operacji.
Na koncu otrzymujemy k bitow tautologii dla calego wyrazenia, i tylko
musimy przejsc po jej bitach zwiekszajac pewnego inta i wylistowac
wszystkie cyfry tego inta gdy bit tautologii jest rowny 1, albo 0, gdy
chcemy wiedziec dla jakich zmiennych wyrazenie nie jest spelnione.
Zbigniew Płotnicki
On 13 Lis, 13:03, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > > > > > > Jeśli wyrażenie nie...
>
> więcej >>
Zbyszek Płotnicki
zwiększa złożoności, Sama funkcja selekcji może być 'wygenerowana' w
czasie 1,
czyli podczas obliczeń, oto algorytm generowania funkcji selekcji:
Zapamiętujemy wszystkie funkcje selekcji w postaci pozycji i, i =
1...k.
Sortujemy je w kolejności rosnącej O(k*log(k)).
Metodą scalania z resztą wyrażenia O(k), czyli gdy pozycja obliczana
równa się
pierwszej z czoła listy tych liczb bierzemy ją uwzględniamy w
obliczeniu
oraz przesuwamy czoło na następną pozycję. W ten sposób koszt
uwzględnienia
wszystkich funkcji selekcji jest równy długości tej listy.
I najbardziej złośliwe wyrażenie pod tym względem:
f ( g(), select[1](), ... , select[k]())
daje złożoność wszystkich obliczeń (2^k + k*(1+log(k)), czyli taką
jaka jest długość danych wejściowych, czyli samej funkcji, ponieważ,
do zapisania nazwy funkcji f potrzebujemy 2^k bitów a do zapisania
kolejnych parametrów k*log(k) bitów.
WYJAŚNIAM TROCHĘ LEPIEJ CAŁY PROCES:
Poprawka:
Nie jest potrzebna żadna tablica, bo zamieniamy w czasie __k*2^k__
korzystając z
_z_samych_wartości_funkcji,_które_są_liczbami_całkowitymi_w_postaci_ciągów_bitów__
tak jak pokazałem (w postaci prostych przykładów) {W systemie
binarnym to będzie w ogólnej postaci: F(G(),H())} na ciąg __2^k___,
skracając tak jak napisałem gdzie indziej o (k-1)*2^k, co czynimy
maksymalnie n/2^k razy,
co daje złożoność ZNALEZIENIA TAUTOLOGII O(n*k) bez użycia żadnych
tablic. Po czym mamy już tylko problem
wylistowania wartości argumentów dla tej tautologii dla których
przyjmuje ona wartość 1 albo 0,
co osiągamy przez zwiększanie pewnej liczby całkowitej od 0 do 2^k i
odczyt
kolejnego pola z liczby całkowitej tautologii,
jeśli jest 1 i szukamy 1 to bierzemy patrzymy na inkrementowany int,
bo jest on równy argumentom
dla jakich ta tautologia przyjmuje wartość 1, bądź 0.
W związku z tym, że użycie przynajmniej jednej funkcji k-argumentowej
powoduje, że dane wejściowe zawierają przynajmniej 2^k bitów,
odczytanie wartości argumentów jest krótsze od wczytania danych
wejściowych.
I to cały algorytm.
Generalnie, co trzeba dodać: nie potrzeba żadnych tablic, żeby w
czasie k*2^k obliczyć tautologię z wyrażenia pojedynczo złożonego,
czyli takiego jakie mamy w każdym kroku skracania całego wyrażenia,
których to kroków jest n*k/2^k,
bo ciąg długości n bitów rozszerzony w każdym argumencie do funkcji
select_a[i]() pomieści maksymalnie n*k/2^k funkcji,
gdyż do zapisania każdej potrzeba 2^k bitów, gdyż jest ona jedną z
liczb : 1..2^k , czyli :
func[i] (func[1], .. func[k]) -> func[j], to zamiana 2^k * k na 2^k,
wyrażenie za to może zawierać tylko n*k/2^k takich funkcji,
a więc w maksymalnie n*k/2^k krokach skracamy całe wyrażenie do
jednej
tautologii. Stąd złożoność czasowa jest:
(n/2^k) {maksymalna ilość wystapień funkcji}
*
k*2^k {czas potrzebny na obliczenie z wartości funkcji będących
parametrami pewnej funkcji, na początku są to użyte funkcje i każdy
parametr w postaci funkcji select_a[i]().}
= n/2^k * k * 2^k = n * k
W związku z tym, że n to rozmiar danych w bitach, otrzymujemy
algorytm
o złożoności maksymalnie:
O(n) <= __O(n*k)__ < O(n^2)
Zbigniew Płotnicki
On 13 Lis, 13:24, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
> ...
>
> więcej >>
Zbyszek Płotnicki
Weźmy najbardziej złośliwy przykład produkujacy najwieksza liczbe
selekcji:
f10( (f20 ( ... ( fn0( g(a), select[1], ... , select[k] ), , select
[1], ... , select[k]) ...), select[1], ... , select[k] )
rozmiar danych wejsciowych > n * 2^k bitów
O: O(2^k * k * n) = O((n*2^k) * k) <= O(rozmiar*k)
Z poważaniem,
Zbigniew Płotnicki
On 14 Lis, 16:09, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> ...
>
> więcej >>
Zbyszek Płotnicki
logiczne
k -symboliczne posiada funkcję tautologią, jedną z przedziału 1.. 2^
(2^k), do zapisania której potrzeba zawsze 2^k bitów. Więc gdy
zapiszemy dowolne wyrażenie logiczne w najprostszej postaci, to
otrzymamy najprostszy w świecie dowód, że algorytm znajdowania
argumentow dla ktorych jest spełnione dowolne wyrażenie posiada
złożoność O(rozmiar danych wejsciowych*k).
Jak wykazałem po pierwsze konwersja dowolnego wyrażenia ma złożoność
O
(n*k).
Ktoś może powiedzieć dobrze, ale przecież możemy psługiwać się tylko
funkcjami binarnymi których jest 16 i można je zapisać w postaci
trzech bitów a nie czterech, albo i tymi i tymi.
Odpowiedź jest bardzo prosta, oto przykład : ((a and b) and c)
dla podwyrażenia a and b, musimy składać tylko funkcje długości 2^2 =
4:
ab|select_a()
-------------
00|0
01|0
10|1
11|1
ab|select_b()
-------------
00|0
01|1
10|0
11|1
ab|a and b = select_a() and select_b()
------------
00|0
01|0
10|0
11|1
wiec mamy tautologie tego wyrazenia w postaci ab->0001, którą
obliczyliśmy w złożoności właściwej dla operacji binarnej teraz
bierzemy select_c()
abc|select_c()
-------------
000|0
001|1
010|0
011|1
100|0
101|1
110|0
111|1
a nastepnie w złożoności właściwej do k-argumentowosci calego
wyrazenia obliczamy tautologię dla juz trzech argumentow:
po pierwsze dublujemy tablice k-1 argumentowa:
ab c|select_a() and select_b()-> c
------------
00 0|0
00 1|0
01 0|0
01 1|0
10 0|0
10 1|0
11 0|1
11 1|1
i dla tych dwóch tablic k argumentowych obliczamy juz całe
wyrażenie :
(a and b) and c = 0001001 and c = and(00000011, 01010101) = 00000001
sprawdzamy :
abc|(a and b) and c
---------------------------
000|0
001|0
010|0
011|0
100|0
101|0
110|0
111|1
===============
teraz ((a and b) or c)
===============
ab c|select_a() and select_b()-> c
------------
00 0|0
00 1|0
01 0|0
01 1|0
10 0|0
10 1|0
11 0|1
11 1|1
i dla tych dwóch tablic k argumentowych obliczamy juz całe
wyrażenie :
(a and b) or c = 0000011 or c = or(00000011, 01010101) = 01010111
sprawdzamy :
abc|(a and b) or c
-------------------------
000|0
001|1
010|0
011|1
100|0
101|1
110|1
111|1
W ten oto sposób obliczyliśmy w czasie O(n*2) wyrażenie oparte na
binarnych funkcjach dla trzech argumentów.
Bo długość odczytanych nazw funkcji to 2^2 + 2^2 = 8, a czas obliczen
to :
1.) 2*4, pierwszy and
2.) 2*8 drugi and
w sumie 3*8 = O(n*k)
Identycznie obliczamy w czasie O(n*k) dowolne wyrażenie oparte na
dowolnych funkcjach.
Zbigniew Płotnicki
On 14 Lis, 17:45, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> ...
>
> więcej >>
Zbyszek Płotnicki
To, że każde wyrażenie logiczne na k symbolach ma tautoligiczną
funkcję wynika z tego, że istnieje jednoznaczne przyporządkowanie
wszystkich możliwych k-tek argumentów do tablicy wyników o wielkości
2^k, a więc każde złożenie dwóch i wielu funkcji także ma funkcję
tautologiczną z nim. i tak aż do uzyskania funkcji tautologicznej dla
całego wyrażenia.
Innymi słowy ktoś musiałby udowodnić, że dowolne wyrażenie o k-
symbolach da się
zapisać krócej niż nazwa funkcji od 1..2^(2^n) co jest niemożliwe.
Oczywiście można preferować jedne funkcje na niekorzyść drugich, ale
nie można skrócić nazw pewnej części funkcji nie wydłużając nazw
innych. Można na przykład używać dla 2 symboli tylko funkcji =>, ale
wtedy nazwy pewnych funkcji będą wykładnicze wobec tej nazwy.
Dla nazw funkcji trzeba przyjąć, że prawdopodobieństwo każdej jest
równe, i dlatego długość także musi być równa, równa 2^n bitów.
Wtedy najkrótszym zapisem dowolnego wyrażenia będzie taka funkcja i
koszt znalezienia wartości dla których jest ona równa 1 albo 0, jest
równy odczytowi jej długości * koszt inkrementacji k-bitowej liczby
calkowitej. = O(n*k).
CND.
----------------------
Co jeszcze ciekawsze z użyciem pamięci możemy rozwiązać to jeszcze
szybciej.
O(n*k) to czas potrzebny na rozwiązanie z użyciem k bitów.
Z użyciem natomiast 2^k bitów pamięci możemy rozwiązać to tak:
W pamięci mamy drzewo liczb k bitowych.
Iterujemy po nim w trakcie przechodzenia przez nazwę funkcji.
Całkowity czas iteracji równy jest liczbie węzłów równej 2^n + 2^n/2
+ ... + 1 = 2*2^k.
Jeśli chcemy wypisać tylko p pierwszych wartosc argumentow dla
ktorych
wyrażenie przyjmuje wartość 0 albo 1,
to całkowity koszt czasowy to:
O(2*2^k + p*k)
---------------------------------------------
Żeby złożoność była O(2*2^k + p*k) wcale nie trzeba drzewa, wystarczy
konstrukcji scieżki na bazie stosu, a więc wystarczy pamięć O(k)
-----------------------------
Oczywiście nazwa funkcji jest tak skonstruowana, że odzwieciedla
kolejno wartości dla kolejnych k-tek możliwych argumentów, kóre
tworzą
ciąg 2^k liczb k bitowych od 1.. 2^k. Jest to możliwe bo takich
wartości jest dokładnie tyle samo, co ilość możliwych funkcji.
--------------------------
Zbigniew Płotnicki
On 16 Lis, 16:34, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> ...
>
> więcej >>
Zbyszek Płotnicki
takim, dla ktorego srednia dlugosc (tym samym sumaryczna dlugosc)
formul o jednakowym prawdopodobienstwie jest najkrotsza.
======================
Dowód:
suma długości będzie
suma(1..i, p(i) * d[i])
gdzie:
p - prawdopodobienstwo symbolu
d - dlugosc symbolu
żeby skrócić zapis symboli przynajmniej o 1 bit trzeba zmniejszyć ich
ilosc o
polowe, czyli otrzymamy nierownosc :
suma(1..2^k, p(i) * d[i]) < suma(1..2^(k-1), p(i) * (d[i] - 1)) +
suma
(1..2^(k-1), p(i) * ((d[j]-1) + (d[k]-1)))
po podstawieniu p(i) = 1/2^k
oraz d[i] = k
otrzymamy :
suma(1..2^k, 1/2^k * k) < suma(1..2^(k-1), 1/(2^k) * (k - 1)) + suma
(1..2^(k-1), 1/(2^k)*[(k - 1) + (k - 1)]))
k * suma(1..2^k, 1) < (k - 1) * suma(1..2^(k - 1), 1) + 2*(k - 1)
*suma(1..2^(k-1),1))
k * suma(1..2^k, 1) < (k - 1) * [suma(1..2^(k - 1), 1) + 2*suma
(1..2^
(k-1),1))]
k * suma(1..2^k, 1) < k * [suma(1..2^(k - 1), 1) + 2*suma(1..2^
(k-1),1))] - [suma(1..2^(k - 1), 1) + 2*suma(1..2^(k-1),1))]
k * suma(1..2^k, 1) < k * suma(1..2^(k - 1), 1) + k * suma(1..2^k,
1)) - suma(1..2^(k - 1), 1) - 2 * suma(1..2^(k-1),1))
0 < k * suma(1..2^(k - 1), 1) - 3 * suma(1..2^(k - 1), 1)
3 * suma(1..2^(k - 1), 1) < k * suma(1..2^(k - 1), 1)
k > 3
=============================
Są jeszcze cztery możliwości:
1.) zmniejszamy o polowe liczbe funkcji i drugą polowe otrzymujemy z
pierwszej przez negację. Możemy to uczynić tylko raz, bo wszystkie
zanegowane funkcje i z pierwszej grupy beda juz w drugiej i vice
versa. kazda funkcja wtedy musi posiadac jeden bit ktory informuje
czy
jest zanegowana czy nie. otrzymujemy wtedy:
suma(1..2^k, 1/2^k * k) = suma(1..2^(k-1), 1/(2^k) * [1 + (k - 1)])
+
suma
(1..2^(k-1), 1/(2^k)*[1 + (k - 1)]))
CND.
2.) zmniejszamy o polowe liczbe funkcji negujac jeden z parametrow.
mozemy tak uczynic log2(k) razy, czyli tyle ile jest argumentow w
funkcji. potrzeba na to log2(k) bitow w funkcji. za kazdym razem
otrzymujemy:
suma(1..2^k, 1/2^k * k) <= suma(1..2^(k-1), 1/(2^k) * [log2(k) + (k
-
1)]) + suma
(1..2^(k-1), 1/(2^k)*[log2(k) + (k - 1)]))
czyli log2(k) >=1, czyli k >= 0.
CND.
3.) zmniejszamy o polowe liczbe funkcji dodajac tylko funkcje negacji
do kazdej funkcji, przy czym zapisujemy ją mniej oszczednie niz w
1.).
robimy to tak, że przed każdą funkcją podajemy ciąg wyznaczajacy
liczbe jej argumentow i przyjmujemy ze jednoargumentowa funkcja jest
tylko jedna. otrzymujemy przed kazda funkcja prefiks log(n):
suma(1..2^k, 1/2^k * k) <= suma(1..2^(k-1), 1/(2^k) * [log2(k) + (k
-
1)]) + suma
(1..2^(k-1), 1/(2^k)*[log2(k) + (k - 1)]))
czyli log2(k) >=1, czyli k >= 0.
CND.
4.) zmniejszamy o polowe liczbe funkcji dodajac tylko funkcje negacji
do kazdej funkcji, przy czym zapisujemy ją mniej oszczednie niz w
3.).
robimy to tak, że przed każdą funkcją podajemy ciąg wyznaczajacy
liczbe jej argumentow i przyjmujemy ze jednoargumentowa funkcji sa 4
(wszystkie). otrzymujemy przed kazda funkcja prefiks log(n):
suma(1..2^k, 1/2^k * k) <= suma(1..2^(k-1), 1/(2^k) * [log2(k) +
log2
(4) + (k - 1)]) + suma
(1..2^(k-1), 1/(2^k)*[log2(k) + log2(4) + (k - 1)]))
czyli log2(k) + log2(4) >=1, czyli k dowolne.
CND.
Udowodoniłem w ten sposób, że system zapisujacy wszystkie funkcje n-
argumentowe przy pomocy 2^n bitów (we wzorach 'k') jest niegorszy lub
lepszy od każdego innego systemu.
Czyli nie można powiedzieć, że mój algortym jest wielomianowy tylko z
powodu nadmiarowego zapisu nazw funkcji, a można powiedzieć, że jest
po prostu wielomianowy dla dowolnego wyrażenia zapisanego przy pomocy
najlepszego pod względem złożoności sposobu zapisu.
=======================
Prawdą jest też, że minimalnym zapisem dowolnej formuły jest funkcja
k
- argumentowa tautoligczna z nią, która ma złożoność wykładniczą
wobec
k, z czego wynika dowód, że :
1.) Istnieje algorytm wielomianowy dla problemu SAT
2.) Nie istnieje algorytm wieliomianowy w sensie W(k) względem
problemu SAT-k, bo samo wczytanie najprostszego zapisu każdego
wyrażenia jest wykładnicze względem k, bo jeśli zawiera choćby jedną
funkcję, to jej nazwa (w minimalnym ogólnym zapisie: bo bierzemy całą
dziedzinę problemu SAT) musi mieć długość wykładniczą względem k, a
nie można wczytać tylko części nazwy funkcji ponieważ funkcje
różniące
się na ostatnim bicie są sobie różne.
Dowodzi to tego, że problem SAT jest P.
Ale dowodzi też tego że nie jest W(k). gdzie W(k) to wielomian.
CND.
=============================
Dowiodłem, że każdy algorytm oparty na innym systemie zapisu wyrażeń
będzie miał średnią złożoność samego odczytu danych nielepszą lub
gorszą od mojego
algorytmu, a zatem także i asymptotyczną złożoność samego odczytu
nielepszą lub gorszą, a zatem każdy inny będzie asymptotycznie
conajmniej wykładniczy wobec liczby
symboli, i conajmniej asymptotycznie wielomianowy względem długości
danych
wejściowych. Dowodzi to też tego, że mój algorytm będzie
asymptotycznie najlepszy, ponieważ ma złożoność asymptotyczną równą
średniej złożoności i nie gorszą od każdego innego algorytmu
i jego złożoność jest w przypadku pojedyńczej
funkcji tautologicznej z całym wyrażeniem asymptotycznie równa
wczytaniu danych O(const * rozmiar danych).
=============================
Co więcej dowolna kompresja wyrażeń dla zbioru wszystkich wyrażeń,
czyli zbioru o równym prawdoopoństwie wszystkich nazw funkcji oraz
równym prawdopodobieństwie wszystkich ustawień funkcji i wszystkich
wyrażeń także doprowadzi do długości funkcji 2^k. CND.
======================
Dowodzi to tego, że funkcja k-argumentowa tautologiczna z całym
wyrażeniem o nazwie długosci 2^k jest najkrótszym możliwym zapisem
dowolnego wyrażenia i jest wykładnicza względem liczby symboli, a
oprócz tego prawdą jest, że mój algorytm wyliczający spelnialność
jest
wielomianowy względem rozmiaru tego wyrażenia. Czyli jest to dowód,
że
problem spełnialności reguł logicznych jest P. CND.
Zbigniew Płotnicki
On 16 Lis, 18:35, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > _z_samych_wartości_funkcji,_które_są_liczbami_całkowitymi_w_postaci_ciągów_-bitów__
> > > > > Co więcej nie trzeba żadnych tablic- Ukryj cytowany tekst -
>
> - Pokaż cytowany tekst -...
>
> więcej >>
Zbyszek Płotnicki
maksymalnie wykładniczy względem liczby symboli, oraz że średnio jest
nie większy od każdego innego systemu. Co oznacza, że średnio każdy
system jest wykładniczy wobec liczby symboli. Jeśli tak zdefinowac NP,
(co jest niesłuszne, bo definiuje się złożonośc względem wielkości
danych wejściowych, a nie jakiejś innej wartości), to żaden system nie
będzie nigdy asymptotycznie wielomianowy, czyli nie będzie P. Co
jednak nie jest prawdą, bo nie można brać liczby symboli jako podstawę
wyliczania złożoności tam gdzie minimalistyczny system zapisu danych
wejściowych jest zawsze (średnio i ogólnie) wykładniczy wobec liczby
symboli. Czyli dowodzi to tego, że samo wczytanie danych będzie zawsze
średnio wykładnicze, czyli nie będzie mogło być nigdy asymptotycznie
wielomianowe względem liczby symboli. Jeśli zatem brac pod uwage
konieczną wielkosc danych wejsciowych dla systemu minimalistycznego,
to okazuje się, że problem należy do P, bo jest wielomianowy wobec
wielkosci danych wejsciowych. Każdy system niegorszy od
minialistycznego będzie miał tę własność, więc wszystkie systemy
minialistyczne będa ją miały. Nawet jeśli nie przyjąć złożoności
wykładniczej długości nazw jako konieczność, to mój algorytm i tak
będzie średnio wielomianowy. Więc jeśliby z kolei tak definiować nie-
NP to algorytm ten jest na mocy tego P.
Dwie rzeczy są pewne:
- zapis względem liczby symboli będzie zawsze średnio wykladniczy, a
minimalistyczny będzie zawsze wykładniczy
- mój algorytm względem tego zapisu będzie zawsze średnio
wielomianowy, a w systemie minimalistycznym po prostu wielomianowy.
Teraz tak:
1.) Jeśli algorytm średnio wielomianowy nie jest NP, czyli jest P, to
SAT jest P, bo mój algorytm jest średnio wielomianowy dla systemu
minimalistycznego.
2.) Jeśli przyjąć system minimalistyczny jako bazę, to algorytm jest
asymptotycznie wielomianowy, czyli po prostu należy do P.
3.) Jeśli przyjać inny system jako bazę, i wnioskować z tego, że dla
pewnych danych algorytm nie jest asymptotycznie wielomianowy, to
algorytm heap sort również nie jest asymptotycznie wielomianowy. Oto
dowód:
Żeby posłużyć się pełną analogią: pewne funkcje k argumentowe (pewien
podzbiór) można wyrazić za pomocą złożenia funkcji mniej
argumentowych. Powoduje to zachowanie wykladnicze mojego algorytmu
wobec dlugosci danych wejsciowych. Identycznie pewne liczby (małe)
można wyrazić jako sumy liczb jeszcze mniejszych, ktore mozna zapisać
posługując się np. dwoma bitami, i zapisać zamiast pełnej liczby (k
bitowej) czterema czy sześcioma bitami. Także zostaje wyrażone to
samo, przy pomocy wykładczniej ilosci pamięci (np 2^5 bitów dla liczb)
kontra niewykładnicza (k*2 bity). Czy algorytm sortowania pełnych 32
bitowych liczb staje się przez to wykładniczy? Oczywiście nie. Tak
samo mój alogrytm nie staje się wykładniczy z tego powodu, że pewien
podzbiór funkcji możemy przedstawić jako złożenie funkcji o nazwach
długości 'podwykładniczej' względem zapisu uniwersalnej funkcji k -
argumentowej.
Dowodzi to tego, że sam fakt, że pewne dane możemy zapisać krócej nie
świadczy o tym, że algorytm nie jest wielomianowy, bo możemy je
zapisać krócej ale nie w systemie minimalistycznym.
Co więcej system zapisujący krócej pewne wyrażenia nie będzie wcale
minimalistyczny, będzie tylko lepszy na krótką metę. Dla całego zbioru
możliwych danych wejściowych będzie nieminimalistyczny, czyli nie może
być podstawą analizy złożoności.
Dowód:
Żeby zapisać krótkie nazwy funkcji potrzeba jednego bitu na ich
odróżnienie. Dodajemy więc do wszystkich symboli 1 bit, aby dla 2 ^ l
funkcji skrócić nazwę do l, gdzie l < d[i], co sprawia, że dane
wejściowe niepotrzebnie rosną, mimo że wydaje się nam że skróciliśmy
zapis.
suma(1..2^k, p(i) * d[i]) < suma(1..2^k - 2 ^ l, p(i) * ( 1 + d[i] ) )
+ suma
(1..2^l, p(i) * l)
suma(1..2^k, d[i]) < suma(1..2^k - 2 ^ l, 1 + d[i]) + suma
(1..2^l, l + 1)
x*suma(1..2^k, 1) < (1+x)*suma(1..2^k - 2 ^ l, 1) + (l + 1) * suma
(1..2^l, 1)
x*suma(1..2^k, 1) < (1+x)*suma(1..2^k, 1) - (1+x)*suma(1..2^l, 1) +
(1 + l) * suma
(1..2^l, 1)
x*suma(1..2^k, 1) < suma(1..2^k, 1) + x*suma(1..2^k, 1) - suma
(1..2^l, 1) - x*suma(1..2^l, 1) + l * suma (1..2^l, 1) + suma (1..2^l,
1)
(x - l)*suma(1..2^l, 1) < suma(1..2^k, 1)
(x - l) < suma(1..2^k, 1) / suma(1..2^l, 1)
(x - l) < 2^(k-l)
x = 1/(2^k)
(1 - l*2^k)/ 2^k < 2^(k-l)
(1 - l*2^k) < 2^(2*k-l)
Zawsze prawdziwe, bo lewa strona jest niedodatnia, a prawa jest
dodatnia.
Co więcej funkcje k - argumentowe zawierają w sobie wszystkie funkcje
mniej argumentowe.
Tym samym udowodniłem, że zapis minimalistyczny jest pełny i że jest
rzeczywiscie minimalistyczny i każda próba jego skrócenia skończy się
wydłużeniem.
Minimalistyczny system, który musi się stać podstawą wyliczania
złożoności po prostu wymaga tego, żeby wyrażenia zapisywać w postaci
pełnych funkcji k-argumentowych.
Co więcej żadnej funkcji nie może w nim zabraknąć, bo jeśliby zabrakło
to rozmiar także by wzrósł - to jest tak proste, że już nie trzeba
wzorów, ale dowiodłem to wcześniej. Także proszę się zapoznać z
wcześniejszymi nierównościami.
4.) Jeśli liczyć średnio wykladniczosc danych wejsciowych, to można
powiedzieć, że algorytm średnio nigdy nie będzie miał złożoności W
(liczba symboli) gdzie W to wielomian, a jeśli oprzeć się na systemie
minimalistycznym, to nie będzie mieć nigdy złożoności wielomianowej
względem liczby symboli.
I tyle mniej więcej da się powiedzieć na ten temat.
Zbigniew Płotnicki
On 20 Lis, 14:54, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > wiec mamy tautologie tego...
>
> więcej >>
Zbyszek Płotnicki
gdzie : d[i] = k, m <= k
suma(1..2^k, p(i) * d[i]) < suma(1..2^k - 2 ^ m, p(i) * ( 1 + d
[i] ) )
+ suma (1..2^l, p(i) * m)
suma(1..2 ^ k, d[i]) < suma(1..2 ^ k - 2 ^ m, 1 + d[i]) + suma
(1..2^m, m + 1)
k * suma(1..2 ^ k, 1) < (1 + k) * suma(1..2 ^ k - 2 ^ m, 1) + (l + 1)
* suma (1..2^m, 1)
k * suma(1..2 ^ k, 1) < (1 + k) * suma(1..2 ^ k, 1) - (1 + k) * suma
(1..2 ^ m, 1) + (m + l) * suma (1..2 ^ m, 1)
k * suma(1..2 ^ k, 1) < suma(1..2^k, 1) + k * suma(1..2^k, 1) - suma
(1..2^m, 1) - k * suma(1..2^m, 1) + m * suma (1..2^m, 1) + suma
(1..2^m, 1)
(k - m) * suma(1..2^m, 1) < suma(1..2^k, 1)
(k - m) < suma(1..2^k, 1) / suma(1..2^m, 1)
(k - m) < 2^(k - m)
x < 2^x prawdziwe dla x >= 0, czyli k - m >= 0, k >= m, czyli
prawdziwe zawsze
Zbigniew Płotnicki
On 22 Lis, 13:27, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> Udowodniłem, że system minimalistyczny jest średnio, minimalnie i
> maksymalnie wykładniczy względem liczby symboli, oraz że średnio jest
> nie większy od każdego innego systemu. Co oznacza, że średnio każdy
> system jest wykładniczy wobec liczby symboli. Jeśli tak zdefinowacNP,
> (co jest niesłuszne, bo definiuje się złożonośc względem wielkości
> danych wejściowych, a nie jakiejś innej wartości), to żaden system nie
> będzie nigdy asymptotycznie wielomianowy, czyli nie będzie P. Co
> jednak nie jest prawdą, bo nie można brać liczby symboli jako podstawę
> wyliczania złożoności tam gdzie minimalistyczny system zapisu danych
> wejściowych jest zawsze (średnio i ogólnie) wykładniczy wobec liczby
> symboli. Czyli dowodzi to tego, że samo wczytanie danych będzie zawsze
> średnio wykładnicze, czyli nie będzie mogło być nigdy asymptotycznie
> wielomianowe względem liczby symboli. Jeśli zatem brac pod uwage
> konieczną wielkosc danych wejsciowych dla systemu minimalistycznego,
> to okazuje się, że problem należy do P, bo jest wielomianowy wobec
> wielkosci danych wejsciowych. Każdy system niegorszy od
> minialistycznego będzie miał tę własność, więc wszystkie systemy
> minialistyczne będa ją miały. Nawet jeśli nie przyjąć złożoności
> wykładniczej długości nazw jako konieczność, to mój algorytm i tak
> będzie średnio wielomianowy. Więc jeśliby z kolei tak definiować nie-NPto algorytm ten jest na mocy tego P.
>
> Dwie rzeczy są pewne:
> - zapis względem liczby symboli będzie zawsze średnio wykladniczy, a
> minimalistyczny będzie zawsze wykładniczy
> - mój algorytm względem tego zapisu będzie zawsze średnio
> wielomianowy, a w systemie minimalistycznym po prostu wielomianowy.
>
> Teraz tak:
> 1.) Jeśli algorytm średnio wielomianowy nie jestNP, czyli jest P, to
> SAT jest P, bo mój algorytm jest średnio wielomianowy dla systemu
> minimalistycznego.
> 2.) Jeśli przyjąć system minimalistyczny jako bazę, to algorytm jest
> asymptotycznie wielomianowy, czyli po prostu należy do P.
> 3.) Jeśli przyjać inny system jako bazę, i wnioskować z tego, że dla
> pewnych danych algorytm nie jest asymptotycznie wielomianowy, to
> algorytm heap sort również nie jest asymptotycznie wielomianowy. Oto
> dowód:
>
> Żeby posłużyć się pełną analogią: pewne funkcje k argumentowe (pewien
> podzbiór) można wyrazić za pomocą złożenia funkcji mniej
> argumentowych. Powoduje to zachowanie wykladnicze mojego algorytmu
> wobec dlugosci danych wejsciowych. Identycznie pewne liczby (małe)
> można wyrazić jako sumy liczb jeszcze mniejszych, ktore mozna zapisać
> posługując sięnp. dwoma bitami, i zapisać zamiast pełnej liczby (k
> bitowej) czterema czy sześcioma bitami. Także zostaje wyrażone to
> samo, przy pomocy wykładczniej ilosci pamięci (np2^5 bitów dla liczb)
> > 1.) Istnieje algorytm...
>
> więcej >>
Zbyszek Płotnicki
1.) gdyby m bylo rowne k, to byloby to bez sensu, bo
stworzylibysmy liczby tej samej dlugosci w dodatku z dodatkowym bitem
na poczatku,
2.) a gdy m < k to tych wartosci jest conajmniej o polowe
mniej od wszystkich ktore mamy pierwotnie, jesli m = k - 1, czyli
jest
dokladnie o polowe mniej to nic sie nie dzieje, bo skracamy dlugosc
polowy po to zeby miec jeden zbior mniejszy o polowe i drugi zbior tej
samej wielkosci
dzieki czemu oszczedzamy 1 bit ktory od razu tracimy bo dopisujemy go
na poczatku
kazdej liczby zeby odroznic oba zbiory i dochodzimy do tego samego co
bylo przed
zmianą, dlatego zeby to w ogole mialo sens m musi byc conajmniej o 2
mniejsze od k, a w takim wypadku wcale nie zmienia sie dlugosc
wartosci ktore pozostaja w pierwotnym zbiorze, czyli wzor jest
prawidlowy i dotyczy przypadku m < k - 1.
Zbigniew Płotnicki
On 22 Lis, 17:12, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > 4.) zmniejszamy o...
>
> więcej >>
Zbyszek Płotnicki
odczytu danych wejsciowych musi byc liczona wobec niego. Gdyby liczyc
zlozonosc wobec jakiegos nieminimalistycznego systemu, to albo uzyska
sie wynik srednio oraz asymptotycznie gorszy (bo ten system
minimalistyczny ma złożoność asymptotyczną równą średniej, czyli jeśli
jakiś algorytm będzie miał średnią gorszą od niego, to będzie też miał
asymptotyczną nie lepszą od swojej średniej czyli gorszą od
asymptotycznej tego systemu), albo dojdzie sie do paradoksow
zlozonosci. Określa on zatem minimalną złożoność samego algorytmu,
czyli dolna granicę jaką trzeba przyjąć dla poszukiwanego algorytmu. W
problemie SAT ta granica to wykładniczość wobec liczby symboli. Jeśli
zatem znajdzie sie algorytm wielomioanowy wobec wielkosci danych
wejsciowych, to bedzie on wielomianowy, mimo że wykladniczy wzgledem
liczby symboli, ponieważ dane wejsciowe są (muszą być) minialnie
wykladnicze wobec liczby symboli. Co więcej algorytm dla
tautologicznej funkcji będącej równoważnikiem wyrażenia ma minimalną
złożoność równą O(const * złożoność wczytania danych), przy zużyciu
pamięci O(log(wielkość wczytania danych)) (warto zauważyć, że
złożoność pamięciowa jest mniejsza od wielkości danych wejściowych,
dzięki temu, że nazwa funkcji zawiera informacje o jej wartościach dla
kolejnych zestawów wartości symboli, więc wystarczy jeden bit dla
odczytu danych wejściowych plus oczywiście k bitów na konstrukcję
scieżki wartości symboli dla kolejnych wartości funkcji
tautologicznej), czyli pod względem złożoności czasowej nic go
asymototycznie nie pobije, a pod względem złożoności pamięci
najprawdopoodobniej też nic go nie pobije. Można udowodnić, że jest to
minimalna pamięć potrzebna dla problemu SAT.
Prosty dowód: do odtworzenia kolejnych wartości k-symboli potrzeba
przynajmniej scieżki inkrementowanej dla każdego nowego zestawu. Można
do tego do pewnej liczby wykorzystać liczbę całkowitą o określonej
liczbie bitów (nie mniejszej niż k), co takze daje złożoność O(log
(wiekosc danych wejsciowych)). Nie ma nic mniejszego od tej scieżki co
może posłużyć do odtworzenia kolejnych zestawów wartości symboli,
ponieważ żeby zinkrementować tę ścieżkę (przechodzącą po wirtualnym
drzewie - pełnym drzewie wszystkich wartości), należy pamiętać ją
całą, ponieważ istnieją przejścia między wartością w postaci P<i> 11..
{k-i razy}...11, a P<i-1>10...{k-i razy}...00, (gdzie P<i> prefiks o
dlugosci i) dla których potrzebna jest modyfikacja całej ścieżki o
długości k-i, w tym o dlugosci k dla i = 0. Problem na konkretnej
maszynie można skrócić do sciezki liczb calkowitych o długości "k/
liczba bitów najwiekszej liczby calkowitej". Ale nadal złożoność
pamięciowa pozostaje log(długość danych wejściowych) tylko i innej
bazie logarytmu.
Więc w parze z tym, że jest to algorytm najlepszy asymptotycznie pod
względem wczytania danych oraz asymtptycznie równy wczytaniu danych
zostało dowiedzione, że jest to najlepszy asymtptycznie algorytm dla
problemu SAT.
Udowodniłem zatem cztery rzeczy:
- problem SAT jest wykladniczy wobec liczby symboli
- problem SAT jest wielomioanowy, czyli należy do P
- mój algorytm jest najlepszy asymptotycznie czasowo
- mój algorytm jest najlepszy asymptotycznie pamięciowo wśród
wszystkich algorytmow które wymagają inkrementowania scieżki wartości
argumentów, czyli prawdopodobnie wśród wszystkich algorytmów, bo tak
niskie wymaganie pamięciowe wynika ze sposobu nazwania funkcji i tego,
że dzięki temu nie trzeba jej wczytywać w całości do pamięci, tylko
wystarczy zapamiętywać jej jeden bit. Każdy inny algorytm będzie
musiał wczytać funkcję w całości co zdominuje opisaną złożoność
konstrukcji scieżki.
Cala prawda:
- każde wyrażenie ma równoważnik w postaci funkcji tautologicznej, bo
jest dokladnie jedno przyporządkowanie 2^k zestawów k różnych symboli
do tablicy wyników o długości 2^k, któremu właśnie odpowiada jedna
funkcja tautologiczna, którą najkrócej można zapisać używając 2^k
bitów.
- zbiór funkcji tautologicznych jest równoważny zbiorowi wszystkich
wyrażeń w tym sensie, że ma takie samo prawodpodobieństwo wszystkich
funkcji oraz każdemu wyrażeniu i każdemu jego podwyrażeniu odpowiada
dokładnie jedna funkcja tautologiczna.
- wystarczy rozważać taki zbior danych wejsciowych
- różnych funkcji jest 2^(2^k)
- do zapisu funkcji potrzeba 2^k bitów
- trzeba odczytać całą funkcję, bo może mieć poszukiwaną wartość
dopiero dla ostatniego zestawu wartosci symboli, stąd złożoność
algorytmu nie będzie nigdy W(k), gdzie W to wielomian.
- maja rowne prawdopobienstwo, wiec ogólnie nie mozna ich skompresowac
w zaden sposob, można tylko kompresować pewien zbiór danych
wejściowych, co nic nie zmienia.
- można w nich zapisać (bo w minimalnym zapisie pomieszczą) wartości
dla kolejnych zestawów wartosci symboli
- mozna zapamietywac tylko jeden bit danych wejsciowych
- pamiec potrzebna na rekonstrukcje (inkrementacje) wartosci symboli
potrzebuje log(dlugosc danych wejsciowych) pamieci, czyli k.
- czas potrzebny na rozwiązanie problemu to wczytanie całych danych
wejsciowych i inkrementacja sciezki o dlugosci k, ktora ma koszt
średni O(1), czyli liniowo wobec wielkosci danych wejsciowych.
Dodatkowo:
- algorytm obliczania funkcji tatologicznej dla dowolnego wyrażenia ma
złożoność O(n*k), gdzie: n - dlugosc danych wejsciowych w bitach, k -
liczba roznych symboli.
I to wszystko.
Zbigniew Płotnicki
On 22 Lis, 17:26, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > zanegowane funkcje i z pierwszej grupy beda juz w drugiej i...
>
> więcej >>
Zbyszek Płotnicki
- mój algorytm jest najlepszy asymptotycznie pamięciowo wśród
wszystkich algorytmow które wymagają inkrementowania scieżki wartości
argumentów, czyli prawdopodobnie wśród wszystkich algorytmów, bo tak
niskie wymaganie pamięciowe wynika ze sposobu nazwania funkcji i
tego,
pamięci, tylko
wystarczy zapamiętywać jej jeden _kolejny_ bit. Każdy inny algorytm
(taki, że nie nazywa funkcji w ten sposób) będzie
musiał wczytać funkcję w całości co zdominuje opisaną złożoność
konstrukcji scieżki.
On 23 Lis, 16:39, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > asymptotycznie wielomianowy, czyli po prostu należy do P....
>
> więcej >>
Zbyszek Płotnicki
"Zapis minimalistyczny jest osiągalnym ideałem zapisu. Złożoność
odczytu danych wejsciowych musi byc liczona wobec niego. Gdyby liczyc
zlozonosc wobec jakiegos nieminimalistycznego systemu, to albo uzyska
ścisłej funkcji] (bo ten system
minimalistyczny ma złożoność asymptotyczną równą średniej, czyli
jeśli
jakiś algorytm będzie miał średnią gorszą od niego, to będzie też
miał
asymptotyczną nie lepszą od swojej średniej czyli gorszą od
asymptotycznej tego systemu)"
Zbigniew Płotnicki
On 23 Lis, 19:18, Zbyszek Płotnicki <zbigniew.plotnicki...@gmail.com>
wrote:
> > > > > wielkosci danych wejsciowych. Każdy system niegorszy od...
>
> więcej >>