OKlibrary  0.2.1.6
Hardness.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 21.6.2011 (Swansea) */
00002 /* Copyright 2011, 2012, 2013 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/Cryptanalysis/Rijndael/data/SmallScaleFieldMulCNF.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Primality/PrimeImplicatesImplicants.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ConflictCombinatorics/HittingClauseSets.mac")$
00027 
00028 kill(f)$
00029 
00030 
00031 /* **********************
00032    * Computing hardness *
00033    **********************
00034 */
00035 
00036 okltest_hardness_cs(f) := block(
00037   assert(f({}) = 0),
00038   assert(f({{}}) = 0),
00039   assert(f({{1}}) = 0),
00040   assert(f({{1,2}}) = 0),
00041   assert(f({{1,2},{-2,3}}) = 1),
00042   assert(f({{1},{1,2},{1,-2}}) = 0),
00043   assert(f({{1,2},{1,-2}}) = 1),
00044   assert(f({{1,2},{-1,2},{1,-2},{-1,-2}}) = 2),
00045   assert(f({{1,2,3},{-1,2},{1,-2},{-1,-2}}) = 2),
00046   assert(f({{1,2,3},{1,-2,3},{1,2,-3},{1,-2,-3}}) = 2),
00047   assert(f(setify(ev_hm(ss_field_rbase_cnfs,[4,2])[2])) = 1),
00048   if oklib_test_level = 0 then return(true),
00049   assert(f(setify(ev_hm(ss_field_rbase_cnfs,[4,3])[2])) = 1),
00050   true)$
00051 
00052 okltest_hardness_u_cs(f) := block(
00053   assert(f({{}}) = 0),
00054   for k : 0 thru if oklib_test_level=0 then 5 else 7 do (
00055    for l : 0 thru if oklib_test_level=0 then 3 else 5 do (
00056      assert(f(smusat_genhorn_cs(k,l)) = min(k,l)) )),
00057   true)$
00058 
00059 
00060 /* **********************************
00061    * Computing propagation-hardness *
00062    **********************************
00063 */
00064 
00065 okltest_phardness_cs(f) := (
00066   assert(f({}) = 0),
00067   assert(f({{}}) = 0),
00068   assert(f({{1}}) = 1),
00069   assert(f({{1,2}}) = 1),
00070   assert(f({{1,2},{-2,3}}) = 1),
00071   assert(f({{1,2},{-1}}) = 1),
00072   assert(f({{1,2},{-1,2}}) = 2),
00073   assert(f({{1,2},{-1,2},{1,-2},{-1,-2}}) = 2),
00074   assert(f({{1,2,3},{-1,2},{1,-2},{-1,-2}}) = 2),
00075   assert(f({{1,2,3},{-1,2,3},{1,-2,3}}) = 2),
00076   assert(f({{1,2,3},{-1,2},{1,-2},{-1,-2}}) = 2),
00077   assert(f({{1,2,3},{-1,2,3},{1,-2,3},{-1,-2,3}}) = 3),
00078   true)$
00079 
00080 /* ************************
00081    * Computing w-hardness *
00082    ************************
00083 */
00084 
00085 okltest_whardness_cs(f) := (
00086   assert(f({}) = 0),
00087   assert(f({{}}) = 0),
00088   assert(f({{},{1}}) = 0),
00089   assert(f({{1},{-1}}) = 1),
00090   assert(f({{1},{-1,2}}) = 1),
00091   assert(f({{1},{2}}) = 0).
00092   assert(f({{1,2},{-1,2}}) = 1),
00093   assert(f({{1,2},{-2,3,4,5}}) = 1),
00094   /* XXX */
00095   true)$
00096 
00097