Jump to ContentJump to Main Navigation

You are looking at 1-11 of 11 items

  • Keywords: NP-complete x
Clear All Modify Search

View:

COMPLEXITY OF SOME PROBLEMS IN MODAL AND INTUITIONISTIC CALCULI

D.M. Gabbay and L. Maksimova

in Interpolation and Definability: Modal and Intuitionistic Logics

Published in print:
2005
Published Online:
September 2007
ISBN:
9780198511748
eISBN:
9780191705779
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780198511748.003.0009
Subject:
Mathematics, Logic / Computer Science / Mathematical Philosophy

This chapter investigates the problem of recognizing properties of logical calculi. Complexity bounds for interpolation and some other problems over Int and S4 are found. It is proved that the ... More


A Formal Theory of Contraction

Neil Tennant

in Changes of Mind: An Essay on Rational Belief Revision

Published in print:
2012
Published Online:
September 2012
ISBN:
9780199655755
eISBN:
9780191742125
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780199655755.003.0004
Subject:
Philosophy, Logic/Philosophy of Mathematics, Metaphysics/Epistemology

This is the heart of the formal theory. Mathematically rigorous definitions are provided of all the formal notions that have been gently introduced in the earlier discussion. The main data type of a ... More


Introduction to combinatorial optimization

Marc Mézard and Andrea Montanari

in Information, Physics, and Computation

Published in print:
2009
Published Online:
September 2009
ISBN:
9780198570837
eISBN:
9780191718755
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780198570837.003.0003
Subject:
Physics, Theoretical, Computational, and Statistical Physics

This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational ... More


Number partitioning

Marc Mézard and Andrea Montanari

in Information, Physics, and Computation

Published in print:
2009
Published Online:
September 2009
ISBN:
9780198570837
eISBN:
9780191718755
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780198570837.003.0007
Subject:
Physics, Theoretical, Computational, and Statistical Physics

Number partitioning is one of the most basic optimization problems. It is very easy to state: ‘Given the values of N assets, is there a fair partition of them into two sets?’ Nevertheless, it is very ... More


The Hardest Problems in NP

Lance Fortnow

in The Golden Ticket: P, NP, and the Search for the Impossible

Published in print:
2017
Published Online:
May 2018
ISBN:
9780691175782
eISBN:
9781400846610
Item type:
chapter
Publisher:
Princeton University Press
DOI:
10.23943/princeton/9780691175782.003.0004
Subject:
Computer Science, Programming Languages

This chapter looks at some of the hardest problems in NP. Most of the NP problems that people considered in the mid-1970s either turned out to be NP-complete or people found efficient algorithms ... More


Dealing with Hardness

Lance Fortnow

in The Golden Ticket: P, NP, and the Search for the Impossible

Published in print:
2017
Published Online:
May 2018
ISBN:
9780691175782
eISBN:
9781400846610
Item type:
chapter
Publisher:
Princeton University Press
DOI:
10.23943/princeton/9780691175782.003.0006
Subject:
Computer Science, Programming Languages

This chapter demonstrates several approaches for dealing with hard problems. These approaches include brute force, heuristics, and approximation. Typically, no single technique will suffice to handle ... More


The Future

Lance Fortnow

in The Golden Ticket: P, NP, and the Search for the Impossible

Published in print:
2017
Published Online:
May 2018
ISBN:
9780691175782
eISBN:
9781400846610
Item type:
chapter
Publisher:
Princeton University Press
DOI:
10.23943/princeton/9780691175782.003.0010
Subject:
Computer Science, Programming Languages

This chapter explores some of today's great challenges of computing. These challenges include parallel computation, dealing with big data, and the networking of everything. The chapter then argues ... More


Representation and Matching of Small Flexible Molecules in Large Databases of 3D Molecular Information

Isidore Rigoutsos and Daniel Platt

in Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications

Published in print:
1999
Published Online:
November 2020
ISBN:
9780195119404
eISBN:
9780197561256
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/oso/9780195119404.003.0013
Subject:
Computer Science, Systems Analysis and Design

In recent years, the need to process and mine available information repositories has been increasing. The variety of the data contained in the targeted databases has given rise to a variety of ... More


Needles in Haystacks

Chris Bleakley

in Poems That Solve Puzzles: The History and Science of Algorithms

Published in print:
2020
Published Online:
October 2020
ISBN:
9780198853732
eISBN:
9780191888168
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/oso/9780198853732.003.0006
Subject:
Mathematics, History of Mathematics, Logic / Computer Science / Mathematical Philosophy

Chapter 6 examines one of the greatest unsolved challenges in mathematics - the problem of finding the best solution from a large number of possibilities. The Traveling Salesman Problem requires that ... More


Universal MemComputing machine

Massimiliano Di Ventra

in MemComputing: Fundamentals and Applications

Published in print:
2022
Published Online:
March 2022
ISBN:
9780192845320
eISBN:
9780191937521
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/oso/9780192845320.003.0005
Subject:
Physics, Theoretical, Computational, and Statistical Physics

This Chapter introduces the formal definition of universal MemComputing machine (UMM). It explains its main features that set it apart from a Turing machine: intrinsic parallelism, functional ... More


The Phase Transition in the Random HornSAT Problem

Demetrios D. Demopoulos and Moshe Y. Vardi

in Computational Complexity and Statistical Physics

Published in print:
2005
Published Online:
November 2020
ISBN:
9780195177374
eISBN:
9780197562260
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/oso/9780195177374.003.0017
Subject:
Computer Science, Mathematical Theory of Computation

This chapter presents a study of the satisfiability of random Horn formulas and a search for a phase transition. In the past decade, phase transitions or sharp thresholds, have been studied ... More


View: