#20920: Changes to Unknown class
-------------------------------------+-------------------------------------
Reporter: eviatarbach | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-7.3
Component: misc | Resolution:
Keywords: days78 | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/eviatarbach/unknown | 7d95643efc6699998240ba08c95006ae4fd9c482
Dependencies: #20919 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
Replying to [comment:6 vdelecroix]:
> Replying to [comment:5 tscrim]:
> > `Undeciable` indicates that there is a stronger statement being made,
e.g., trying to determine if two finitely presented groups are isomorphic,
whereas `Unknown` simply says the algorithm (currently) cannot determine a
solution.
>
> Let me try to make clearer my point. When you ask the question
`are_isomorphic(G1, G2)` this has an answer: either `True` or `False`. As
you said, despite the 1001 heuristics implemented, it might be that the
algorithm you have does not have anything relevant to say. However,
returning `Undecidable` is a complete nonsense. The problem
`are_isomorphic` ('''without parameters''') is undecidable but the
instance `are_isomorphic(G1, G2)` is always decidable.
My understanding is that the isomorphism problem (determining if `G1` and
`G2` are isomorphic) for finitely-presented groups is undecidable. At
least for the word problem (if two reduced expressions represent the same
element) in a finitely-presented group, it is undecidable:
https://en.wikipedia.org/wiki/Word_problem_for_groups. Heuristics in this
case are usually checks to show things are not equal, e.g., checking if
some of invariant is different.
However, this is different than the case when we don't know if something
is undeciable, in that there might exist some algorithm which we don't yet
know of. These are often more closely tied with constructions of objects,
like constructing strongly regular graphs (I believe). So I feel that
having an `Undeciable` allows us to carry more information to the user
that they are trying to do something that is impossible.
--
Ticket URL: <https://trac.sagemath.org/ticket/20920#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
