Sorting nine inputs requires twenty-five comparisons

DOI10.1016/J.JCSS.2015.11.014zbMATH Open1333.68087OpenAlexW2208979138MaRDI QIDQ899586FDOQ899586

Authors: Michael Codish, Luís Cruz-Filipe, M. Frank, Peter Schneider-Kamp 

Publication date: 30 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2015.11.014

Recommendations

• A computer-assisted optimal depth lower bound for nine-input sorting networks
• Optimal sorting networks
• Optimal-depth sorting networks
• New Bounds on Optimal Sorting Networks
• Sorting networks: to the end and back again

zbMATH Keywords

symmetry breakingSAT solvingsorting networkscomputer-assisted proofs

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• Efficient CNF encoding of Boolean cardinality constraints
• Interactive theorem proving and program development. Coq'Art: the calculus of inductive constructions. Foreword by Gérard Huet and Christine Paulin-Mohring.
• The challenge of computer mathematics
• Sorting in \(c \log n\) parallel steps
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• Boolean equi-propagation for concise and efficient SAT encodings of combinatorial problems
• Optimal sorting networks
• Title not available (Why is that?)
• Bounds on the size of test sets for sorting and related networks
• Efficient generation of the binary reflected gray code and its applications
• Toward a lower bound for sorting networks
• Formalizing size-optimal sorting networks: extracting a certified proof checker
• A Sorting Problem
• Optimizing a Certified Proof Checker for a Large-Scale Computer-Generated Proof
• Extraction in Coq: An Overview
• An Improved Lower Bound for Sorting Networks

Cited In (13)

• Optimizing a Certified Proof Checker for a Large-Scale Computer-Generated Proof
• Sorting networks: to the end and back again
• Expressing symmetry breaking in DRAT proofs
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• How to get more out of your oracles
• The half cleaner lemma: constructing efficient interconnection networks from sorting networks
• Optimal conclusive sets for comparator networks
• Logic Programming with Graph Automorphism: Integratingnautywith Prolog (Tool Description)
• Optimal-depth sorting networks
• Formalizing size-optimal sorting networks: extracting a certified proof checker
• Optimizing sorting algorithms by using sorting networks
• Formally proving size optimality of sorting networks
• Optimal sorting networks

This page was built for publication: Sorting nine inputs requires twenty-five comparisons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899586)