Recent content by complexity9

*bump* anyone know how to solve this? help...

I have been trying to solve the problem in part (vi) for almost a whole week, but still not able to solve it. Please read the attachment before proceeding. I was able to show that, using part (iii), we can construct a deterministic program S from P. Then S gives the same outcome as G for the...

Please do think about it and let me know! This question is so hard, took me so long just to get anywhere. EDIT: I think I may have found an algorithm for satisfiability for ALL of them in PSPACE. Let me describe it and see what you think. The algorithm go as follows: Since we have a...

Okay let me summarize what I think you have said, just to make sure we are on the same page (I am a bit confused at this point, lol): So the first problem was reducible to SAT, that's fine. The problems 2-4 are all decidable. The 2nd problem (boolean combination of existentially-bounded...

But how come k is bounded by a constant in the first two cases (with no predicate/function variables), then when you allow for predicate/function variables, k suddenly becomes unbounded (by a constant). What I mean is, why can't predicate symbols have growth as fast as 2^(n^n), if it has arity...

But you only need to consider those predicate variables that are "written down" in the sentence. In order for it to be written down, it must have some finite arity. What I'm saying is, if a predicate variable P is written down such as P(x,y,z,z,x,w) or however many arity you want (as long as its...

Thank you for that! Your argument is very nice and simple (compared to the one I came up with earlier, which proved that it is PSPACE, but took two pages in latex). Anyway, it seems like this idea can be applied to the boolean combination of existentially-bounded L^P sentences as welll; since we...

Citan Uzuki, Do you mind helping me with another question. It is based on an extension of the first question in this thread. Basically, what happens when you take a boolean combination of the existentially-bounded sentence (without equality or function symbols)? Please see the image for...

By the way, can equality be written from function variables and predicate variables? For example, if you have a FO logic vocabulary with everything but equality, is this equavalent to the normal FO logic vocabulary?

Okay ignore the above. I had misunderstood of the problem to begin with, but I now understand. The "satisfiability" problem asks if there is a model that satisfies our existentially bounded sentence; if we have for example P(x,y) and P(y,z), we just simply define them to be different in our...

Can you elaborate on this? What if we have P(x,y) and P(y,z) and Q(x,y) and Q(z,x,y). What do you say about their equality? Do you just assign different predicate variables to each of them? But are they not "related" somewhat to one another (since they share x,y or z)? What is Q is defined to...

An NFA (nondeterministic finite automaton) is acyclic if there is no path from a state to itself. Decision problem: Given two acyclic NFAs A and B, does L(A)=L(B), i.e. does A accept the same language as B. Show that the above decision problem is NP-Complete. I am unable to show that it...

I have been thinking about this question for weeks and can't figure it out! I reckon it's decidable and in EXPTIME, but not sure how to prove this! Any help would be reallllly appreciated! (Note: the question is in the attachment) -Peter