8
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: not found
      • Book Chapter: not found
      Feasible Mathematics II 

      On Frege and Extended Frege Proof Systems

      other
      Birkhäuser Boston

      Read this book at

      Buy book Bookmark
          There is no author summary for this book yet. Authors can add summaries to their books on ScienceOpen to make them more accessible to a non-specialist audience.

          Related collections

          Most cited references38

          • Record: found
          • Abstract: not found
          • Article: not found

          Parity, circuits, and the polynomial-time hierarchy

            Bookmark
            • Record: found
            • Abstract: found
            • Article: not found

            The relative efficiency of propositional proof systems

            We are interested in studying the length of the shortest proof of a propositional tautology in various proof systems as a function of the length of the tautology. The smallest upper bound known for this function is exponential, no matter what the proof system. A question we would like to answer (but have not been able to) is whether this function has a polynomial bound for some proof system. (This question is motivated below.) Our results here are relative results.
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              The intractability of resolution

                Bookmark

                Author and book information

                Book Chapter
                1995
                : 284-319
                10.1007/978-1-4612-2566-9_10
                c359ab87-3d17-4019-baf7-1bbc843a3095
                History

                Comments

                Comment on this book

                Book chapters

                Similar content2,516

                Cited by4