On recognition complexity for systems of functions in the class \(P^*_3\) (Q1280364): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q593066 |
||
Property / reviewed by | |||
Property / reviewed by: Anatoly Martynyuk / rank | |||
Revision as of 03:36, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On recognition complexity for systems of functions in the class \(P^*_3\) |
scientific article |
Statements
On recognition complexity for systems of functions in the class \(P^*_3\) (English)
0 references
15 March 1999
0 references
Let \(P^*_k\) be the set of all partial functions of \(k\)-valued logic and \(P_k\) be the set of everywhere defined functions from \(P^*_k\). The authors discuss the complexity of an algorithm which recognizes the completeness of systems of functions in the class \(P^*_3\) with respect to superposition. It is assumed that the functions are defined by the vectors of their values for a fixed order of the sets of variables. In addition, non-branching bit calculations are taken as algorithms. The authors prove that there exists an algorithm with bit complexity \(O(N^{\log_36}\log_2^2N)\), where \(N\) is the length of the input information.
0 references
completeness of systems of functions
0 references
class \(P^*_3\)
0 references
recognition complexity
0 references
partial many-valued logic functions
0 references