On recognition complexity for systems of functions in the class \(P^*_3\) (Q1280364): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: MaRDI profile type (P1460): MaRDI publication profile (Q5976449), #quickstatements; #temporary_batch_1710461151948 |
||
(2 intermediate revisions by one other user not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Anatoly Martynyuk / rank | |||
Property / reviewed by | |||
Property / reviewed by: Anatoly Martynyuk / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 09:37, 15 March 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