View:

- no detail
- some detail
- full detail

## 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

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

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

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

View:

- no detail
- some detail
- full detail