AC0
AC 0 jest klasą złożoności stosowaną w złożoności obliczeniowej obwodów logicznych. Jest to najmniejsza klasa w hierarchii AC i składa się ze wszystkich rodzin obwodów o głębokości O(1) i wielkości wielomianowej, z nieograniczonym stopniem wejścia bramek AND i bramek OR (dopuszczamy bramki NIE tylko na wejściach). W ten sposób zawiera NC0, który ma tylko ograniczony stopień wejścia bramek AND i OR.
AC 0 jest klasą złożoności stosowaną w złożoności obliczeniowej obwodów logicznych. Jest to najmniejsza klasa w hierarchii AC i składa się ze wszystkich rodzin obwodów o głębokości O(1) i wielkości wielomianowej, z nieograniczonym stopniem wejścia bramek AND i bramek OR (dopuszczamy bramki NIE tylko na wejściach)[1]. W ten sposób zawiera NC0, który ma tylko ograniczony stopień wejścia bramek AND i OR.
Przykładowe problemy
[edytuj | edytuj kod]Dodawanie i odejmowanie liczb całkowitych jest obliczalne w AC0[2], ale mnożenie nie jest (przynajmniej nie w zapisie binarnym i dziesiętnym).
Przypisy
[edytuj | edytuj kod]- ↑ Boaz Barak, Computational complexity : a modern approach, Cambridge: Cambridge University Press, 2009, ISBN 978-0-521-42426-4, OCLC 286431654 [dostęp 2020-02-02].
- ↑ http://people.clarkson.edu/~alexis/PCMI/Notes/lectureB02.pdf