Dear Xudong,
the conservative worstcase complexity bound is O(2^n), where n is the
number of atoms in a ground program output by Gringo. This is because
each atom has two possible values, true or false, so that 2^n
assignments are constructible. If a program doesn't belong to a
tractable class (e.g. stratified), there are no better guarantees on
solving time in the worst case.
The worstcase time/space complexity of instantiation by Gringo is even
greater. It correlates to the number of variables occurring jointly in
rules. However, given a fixed nonground enconding, one can probably
approximate the number of resulting ground atoms relative to facts in an
instance. This yields the n in the bound O(2^n) on solving.
Cheers,
Martin
On 11/20/2012 06:48 AM, Xudong Liu wrote:
> Hi all,
>
> I am doing a class project for graduate school. My C++ codes apply
> gringo/clasp as a back solver system in order to compute a combinatorial
> subproblem in the project since I felt much easier to program in
> gringo/clasp than directly do it in C++. But I also need to know the
> time complexity of using gringo/clasp for later writeups.
>
> So given an input file (data+rules w\ variables) accepted by gringo, how
> do I calculate, or approximate, the time complexity of gringo/clasp
> using bigO notation? As far as I know, one can approximate the number
> of lines in the ground program grounded by gringo based on the domains
> of variables and the rules in the input file. If we denote the number
> of lines in the ground program as n, is the number of lines in the
> ground Dimacs program O(n) or something else? Is then the time
> complexity of the solver clasp O(n) or something else?
>
> Thank you very much.
>
> 
> Best Regards,
> Xudong
>
>
>
> 
> Monitor your physical, virtual and cloud infrastructure from a single
> web console. Get indepth insight into apps, servers, databases, vmware,
> SAP, cloud infrastructure, etc. Download 30day Free Trial.
> Pricing starts from $795 for 25 servers or applications!
> http://p.sf.net/sfu/zoho_dev2dev_nov
>
>
>
> _______________________________________________
> Potasscousers mailing list
> Potasscousers@...
> https://lists.sourceforge.net/lists/listinfo/potasscousers
>
