On maximal and minimal elements of partially ordered sets of Boolean degrees |
| |
Authors: | S S Marchenkov |
| |
Institution: | 1. LomonosovMoscow State University, Leninskie gory, Moscow, 119991, Russia
|
| |
Abstract: | The paper addresses the “weakest” algorithmic reducibility—Boolean reducibility. Under study are the partially ordered sets of Boolean degrees L Q corresponding to the various closed classes of Boolean functions Q. The set L Q is shown to have no maximal elements for many closed classes Q. Some examples are given of a sufficiently large classes Q for which L Q contains continuum many maximal elements. It is found that the sets of degrees corresponding to the closed classes T 01 and SM contain continuum many minimal elements. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|