"On P versus NP cap co-NP for Decision Trees and Read-Once Branching Programs." . . . . . . "Savick\u00FD, Petr" . "N/A" . "On P versus NP cap co-NP for Decision Trees and Read-Once Branching Programs."@en . "357;370" . "8" . . "RIV/67985807:_____/99:06020141" . "Razborov, A." . "On P versus NP cap co-NP for Decision Trees and Read-Once Branching Programs." . "It is known that if a Boolean function f in n variables has a DNF and a CNF of size at most N then f also has a decision tree of size exp(O(log n log^2 N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require decision trees of size exp(Omega)log^2 N)) where N is the total number of monomials in minimal DNFs for f and not f. Moreover, we exhibit new exponential lower bounds on read-once branching program size for explicit Boolean functions." . "P(GA201/95/0976), Z(AV0Z1030915)" . "1016-3328" . . . . . "[A489F02C6866]" . "Wegener, I." . "14"^^ . "On P versus NP cap co-NP for Decision Trees and Read-Once Branching Programs."@en . "Computational Complexity" . . . . "computational complexity; Boolean functions; decision trees; branching programs; P versus NP intersection co-NP"@en . . . "CH - \u0160v\u00FDcarsk\u00E1 konfederace" . "1"^^ . . "748421" . . "0"^^ . "4"^^ . "RIV/67985807:_____/99:06020141!RIV/2003/AV0/A06003/N" . . "It is known that if a Boolean function f in n variables has a DNF and a CNF of size at most N then f also has a decision tree of size exp(O(log n log^2 N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require decision trees of size exp(Omega)log^2 N)) where N is the total number of monomials in minimal DNFs for f and not f. Moreover, we exhibit new exponential lower bounds on read-once branching program size for explicit Boolean functions."@en . "0"^^ . . "Jukna, S." .