tag:blogger.com,1999:blog-3722233.post2603539430702146180..comments2024-09-12T13:59:27.670-05:00Comments on Computational Complexity: Inverse Closure ProblemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-54788333068853257082012-12-02T14:00:49.481-06:002012-12-02T14:00:49.481-06:00If you mean only finite unions and intersections, ...If you mean only finite unions and intersections, we have<br /><br />2 HS all closed subsets of R^D<br />2 HS all open subsets of R^D<br />2 HS all countable subsets of R^D<br /><br />4 HS all uncountable subsets of R^D<br /><br />7 HS++ subspaces of a vector space<br />7 HS++ ideals in a ring (generalization of subspaces and vector spaces)NP Slaglehttps://www.blogger.com/profile/06322388966706601689noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85610392752717038472012-11-29T12:00:31.731-06:002012-11-29T12:00:31.731-06:00Amir Ben-Armram emailed me about DCFL but also ema...Amir Ben-Armram emailed me about DCFL but also emailed me some nice<br />geometric ones:<br /><br />Set of all half-closed planes: NONE<br /><br />Set of all lattice points in half-closed planes: Only COMPGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28516899759622047362012-11-28T12:42:26.245-06:002012-11-28T12:42:26.245-06:00For 8. UNION-NO, INTER-NO, COMP-NO:
Perhaps the s...For 8. UNION-NO, INTER-NO, COMP-NO:<br /><br />Perhaps the set of all 1-element subsets of N.<br />Or the set of all 3-element subsets of N.<br /><br />Or the set of all circles (interpreted as point sets).<br />Or the set of all lines.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49202881219455989702012-11-28T02:21:43.165-06:002012-11-28T02:21:43.165-06:006-CT: The class of all deterministic context-free
...6-CT: The class of all deterministic context-free<br />languages is closed under complements, <br />not closed under union, and hence not closed under intersection.frederikhttp://bar.foo.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82888258187293458732012-11-27T11:56:20.626-06:002012-11-27T11:56:20.626-06:00Amir Ben-Amram emailed me the following but is ha...Amir Ben-Amram emailed me the following but is having a hard time convincing the blog that he is not a robot, so I post for him:<br /><br />UNION-NOT, INTER-NOT, COMP-NOT: Set of all reg langs<br />that have a MIN DFA with exactly 1 accepting state.<br />(1 can be replaced by other numbers)<br /><br />UNION-NOT, INTER-YES, COMP-NOT: Set of all reg langs<br />that have a DFA (not necc minimal) with exactly 1 accepting<br />state. Note that the accepting state need not be reachable.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62541600312581363992012-11-27T07:57:01.578-06:002012-11-27T07:57:01.578-06:00AH- typo in my blog- here is what I meant.
So- doe...AH- typo in my blog- here is what I meant.<br />So- does this work:<br /><br />Let a<b<br /><br />set of regular langs such that the minimal DFA for it<br />has b states of which a are accepting.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18893167346230268622012-11-27T06:24:01.813-06:002012-11-27T06:24:01.813-06:008-CT is actually closed under complement. For any ...8-CT is actually closed under complement. For any language represented by a DFA with >= 1 accepting state, just complement the set of accepting states. The only language represented by a DFA with 0 accepting states is the empty language, whose complement can be represented with a single state.<br /><br />I think the pair (k+2,k) might be immune to this problem, but (k+1, k) is always closed under complement.FMotahttps://www.blogger.com/profile/14394936561912046612noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57559850503685596192012-11-26T15:52:44.438-06:002012-11-26T15:52:44.438-06:007HS: sets of size at most k.
8HS: sets of size exa...7HS: sets of size at most k.<br />8HS: sets of size exactly k.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32269351084091089982012-11-26T15:01:32.427-06:002012-11-26T15:01:32.427-06:00GREAT- Yes that works.
Are there others? (Probabal...GREAT- Yes that works.<br />Are there others? (Probabaly)<br />Are there others that are more natural (I hope so but I doubt it)GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33993370375929693572012-11-26T14:48:27.862-06:002012-11-26T14:48:27.862-06:00For 7 CT, how about co-CFL?For 7 CT, how about co-CFL?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62954883232836418582012-11-26T13:55:46.689-06:002012-11-26T13:55:46.689-06:00YES- { {a}, {b} } works for a class that is NOT cl...YES- { {a}, {b} } works for a class that is NOT closed<br />under UNION, INTER or COMP.<br /><br />Still want a more natural example, or for that matter<br />just other examples of a different character.<br /><br />THANKS!<br /><br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52639400784647650992012-11-26T13:40:51.066-06:002012-11-26T13:40:51.066-06:00Why not something similar to 7 for 8? Why not something similar to 7 for 8? Anonymousnoreply@blogger.com