Advertisement
Published in:
2012 | OriginalPaper | Chapter
Bounded Time
Author : Stasys Jukna
Published in: Boolean Function Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this chapter we show a time-size tradeoff for nondeterministic branching programs. By the
size
of a program in this chapter we will mean the number of nodes, not just the number of labeled edges. A program computes a given function
in time
T if every accepted input has at least one accepting computation of length at most T.