ISSN:
1572-9273
Keywords:
adversary
;
evasiveness
;
recognition complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n 2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k ≤ n 2 / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1006422023869
Permalink
