The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph
The first part of this thesis considers the complexity of Boolean functions. The main complexity measures used are the number of gates in combinational networks and the size of Boolean formulas. The case of monotone realizations, using only the operations AND and OR, of monotone functions is emph...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149519 |
| _version_ | 1811070914891087872 |
|---|---|
| author | Bloniarz, Peter Anthony |
| author2 | Meyer, Albert R. |
| author_facet | Meyer, Albert R. Bloniarz, Peter Anthony |
| author_sort | Bloniarz, Peter Anthony |
| collection | MIT |
| description | The first part of this thesis considers the complexity of Boolean functions. The main complexity measures used are the number of gates in combinational networks and the size of Boolean formulas. The case of monotone realizations, using only the operations AND and OR, of monotone functions is emphasized. |
| first_indexed | 2024-09-23T08:43:38Z |
| id | mit-1721.1/149519 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:43:38Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1495192023-03-30T04:18:42Z The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph Bloniarz, Peter Anthony Meyer, Albert R. The first part of this thesis considers the complexity of Boolean functions. The main complexity measures used are the number of gates in combinational networks and the size of Boolean formulas. The case of monotone realizations, using only the operations AND and OR, of monotone functions is emphasized. 2023-03-29T15:04:10Z 2023-03-29T15:04:10Z 1980-06 https://hdl.handle.net/1721.1/149519 MIT-LCS-TR-238 application/pdf |
| spellingShingle | Bloniarz, Peter Anthony The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph |
| title | The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph |
| title_full | The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph |
| title_fullStr | The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph |
| title_full_unstemmed | The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph |
| title_short | The Complexity of Monotone Boolean Functions and an Algorithm for Finding Shortest Paths on a Graph |
| title_sort | complexity of monotone boolean functions and an algorithm for finding shortest paths on a graph |
| url | https://hdl.handle.net/1721.1/149519 |
| work_keys_str_mv | AT bloniarzpeteranthony thecomplexityofmonotonebooleanfunctionsandanalgorithmforfindingshortestpathsonagraph AT bloniarzpeteranthony complexityofmonotonebooleanfunctionsandanalgorithmforfindingshortestpathsonagraph |