Graph complexity |
| |
| Authors: | Pavel Pudlák Vojtěch Rödl Petr Savický |
| |
| Affiliation: | (1) Mathematical Institute  SAV,  itná 25, 1 Praha, Czechoslovakia;(2) Department of Mathematics, FJFI VUT, Husova 5, 1 Praha, Czechoslovakia;(3) Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 1 Praha, Czechoslovakia |
| |
| Abstract: | Summary We develop a complexity theory based on the concept of the graph instead of the Boolean function. We show its relation to the Boolean complexity and prove some lower bounds to the complexity of explicitly given graphs.The paper was written while the first author was visiting Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
