rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Nondeterminism and optimization
  name:
    name part: Cai, Liming.
    role:
      role term: creator
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: xx
    date issued: 1994
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: print
    extent: ix, 153 leaves : illustrations ; 28 cm.
  abstract: The study of the power of nondeterminism is central to complexity theory. However, it remains unclear how nondeterminism can be used to characterize computational optimization problems. In this dissertation, a "Guess-then- Check" model GC is introduced to systematically study nondeterminism. Techniques are developed to construct GCcomplete languages and to improve recent results in the study of nondeterministic computation. GC computations with weak checkers are studied in detail based on precise circuit characterizations of logaxithraic-time alternating Turing machines. The complexity, fixed-parameter tractability, and approximability of NP optiraization problems are extensively investigated based on GC computations with weak checkers. It is shown that the complexity of solution size-bounded optimization problems is precisely described by their usage of nondeteranism. It is also proved that:hxed-paxameter tractability and intractability of parameterized problems axe exactly characterized by different amounts of nondeterminism. A close relationship between the fixed-parameter tractability and the approximability of NP optimization problems is well established to study the nondeterminism characterization of approximability. Evidence is presented that our research gives a new insight into the computational properties of optimization problems.
  note: by Liming Cai.
  note: Vita.
  note: "Major Subject: Computer Science".
  note: Issued also on microfiche from University Microfilms Inc.
  note: Includes bibliographical references.
  note: Ph. D. Texas A&M University 1994.
  subject:
    topic: Major computer science
  identifier: 95-20319 UMI
  identifier: http://hdl.handle.net/1969.1/DISSERTATIONS-1556666
  identifier: http://proxy.library.tamu.edu/login
  related item:
    location:
      url: http://hdl.handle.net/1969.1/DISSERTATIONS-1556666
  related item:
    location:
      url: http://proxy.library.tamu.edu/login
  record info:
    record content source: TXA
    record creation date: 960618
    record change date: 20210803090545.0
    record identifier: in00001308056