http://openproblemgarden.org/op/fixed_point_logic_with_counting Comments for "Fixed-point logic with counting" en http://openproblemgarden.org/op/fixed_point_logic_with_counting <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/blass_andreas">Blass</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/logic">Logic</a> » <a href="/category/finite_model_theory">Finite Model Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Question</b>&nbsp;&nbsp; Can either of the following be expressed in fixed-point logic plus counting:<br /> <ol class="enumerate"> \item Given a graph, does it have a perfect matching, i.e., a set <img class="teximage" src="/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png" alt="$ M $" /> of edges such that every vertex is incident to exactly one edge from <img class="teximage" src="/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png" alt="$ M $" />? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant? </ol> </div> </tr></td> </table> </td> </tr> </table> Blass, Andreas Capturing PTime counting quantifiers Fixed-point logic FMT03-Bedlewo Logic Finite Model Theory http://openproblemgarden.org/op/fixed_point_logic_with_counting#comment Fri, 18 May 2012 02:09:55 +0200 dberwanger 37424 at http://openproblemgarden.org