TY - GEN

T1 - Complexity issues for preorders on finite labeled forests

AU - Hertling, Peter

AU - Selivanov, Victor

PY - 2011/9/26

Y1 - 2011/9/26

N2 - We prove that three preorders on the finite k-labeled forests are polynomial time computable. Together with an earlier result of the first author, this implies polynomial-time computability for an important initial segment of the corresponding degrees of discontinuity of k-partitions on the Baire space. Furthermore, we show that on ω-labeled forests the first of these three preorders is polynomial time computable as well while the other two preorders are NP-complete. © 2011 Springer-Verlag.

AB - We prove that three preorders on the finite k-labeled forests are polynomial time computable. Together with an earlier result of the first author, this implies polynomial-time computability for an important initial segment of the corresponding degrees of discontinuity of k-partitions on the Baire space. Furthermore, we show that on ω-labeled forests the first of these three preorders is polynomial time computable as well while the other two preorders are NP-complete. © 2011 Springer-Verlag.

UR - http://www.scopus.com/inward/record.url?scp=80053029158&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-21875-0_12

DO - 10.1007/978-3-642-21875-0_12

M3 - Conference contribution

AN - SCOPUS:80053029158

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 112

EP - 121

BT - Models of Computation in Context (CiE 2011)

T2 - computability in europe-2011

Y2 - 27 June 2011

ER -