5
Wiem, że boomska satysfakcja jest NP-Complete, ale jest minimalizacją/uproszczeniem wyrażenia boolowskiego, przez co rozumiem przyjęcie danego wyrażenia w symbolicznej formie i wytworzenie równoważnego, ale uproszczonego wyrażenia w formie symbolicznej, NP-Complete? Nie jestem pewien, czy istnieje redukcja do satysfakcji z minimalizacji, ale wydaje mi się, że prawdopodobnie istnieje. Czy ktoś wie na pewno?Czy minimalizacja wyrażeń boolowskich NP-Complete?
Napisane nieco bardziej starannie może to być obniżka, której szukał. –
Ty i oryginalny plakat prawdopodobnie oznacza NP-trudne. O ile mogę się dowiedzieć, problem nie jest znany w NP. – starblue
starblue: nie, mamy na myśli NP kompletny. SAT jest w rzeczywistości klasycznym NP kompletnym problemem, tj. Był to pierwszy problem udowodniony jako NP kompletny, a wszystkie inne są bezpośrednio lub pośrednio zredukowane do niego. Tak nawiasem mówiąc, wszystko to zostało wyjaśnione w artykule w Wikipedii. –