From: Xudong L. <xud...@gm...> - 2012-11-20 05:48:20
|
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 big-O 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 |
From: Martin G. <ge...@cs...> - 2012-11-20 08:15:22
|
Dear Xudong, the conservative worst-case 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 worst-case 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 non-ground 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 big-O 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 in-depth insight into apps, servers, databases, vmware, > SAP, cloud infrastructure, etc. Download 30-day Free Trial. > Pricing starts from $795 for 25 servers or applications! > http://p.sf.net/sfu/zoho_dev2dev_nov > > > > _______________________________________________ > Potassco-users mailing list > Pot...@li... > https://lists.sourceforge.net/lists/listinfo/potassco-users > |