**Problem:**Give a single theorem that characterizes the theorems 1, corollaries 1/2 and skewed variations of corollaries 1/2. In other words, give a characterization of the computability of an SURE defined over an arbitrary polyhedral unbounded domain.

**Explanation:**The domain could be

The statement of computability may be the following:

An SURE defined over an arbitrary unbounded polyhedral domain is incomputable iff

Some assumptions

We have two cones

The convex cone of the (negative) dependence vectors strictly contains all the vectors which are the weight of cycles. Also, containing vectors just means of the same direction It could contain vectors which cannot be expressed by cycles of the weight vectors.

What has the separability of these two cones have to do with computability?: If C1 and C2 are separable, then of course the SURE is computable.

A sufficient condition for computability: If there exists a cycle whose weight is a vector that belongs to the two cones, then the SURE is incomputable. The weight vector of a cycle ofcourse belongs to a cycle. Does it belong to the char.cone of the domain?

How does the computability condition of SURE change if the domains are non-polyhedral, but still convex?

The concept of char.cone is from polyhedral domains. According to the book and lecture notes of Bertsekas et.al, the concept is perfectly valid in every convex domains. There are some caveats though. ????

Notes about importance of computability problem of S*RE's defined on unbounded Vs. bounded domains. According to QS,

*Unbounded domains are not that important while bounded domain are*. This is because, they are more common. I disagree with this. More importantly, however, QS make the important observation that the computability problem of bounded domains is equivalent to the testing of the acyclicity of the EDG. From the outside, this seems like a condition which can be applied only to a non-parametrtized domain. However, thinking of the parameters as additional dimensions is a standard trick.

So, the question is given a bounded domain, and a computation defined over it, what is the computability problem?

**Problem:**An SURE defined over a bounded domain is computable iff, there exists no zero weight cycle.

**Restatement of the problem:**Given a partially integral polytope -- meaning some vertices are integral, others are rational -- find whether the polytope contains the vertex {0}

**Algorithm:**Use KMW decomposition. Find which edges donot participate in any cycle, remove them, recurse on the rest of the graph.

Question on

*finitizabilty*of the domains

Later note:

I had originally defined the finitizability so the the computability condition of COR.1/2 of KMW can be applied to the case of SUREs defined over the skewed domains of COR.1/2.

Later note: With the precison we have for the condition for computability, we donot need this "finitizability".

**Question:**Given a computation defined over an unbounded polyhedral domain.

**To find:**A skew of the domain such that the application of which results in the maximization of for loops.

Example1: if given a computation defined over Q_t * F_(n-t) (ala domain of cor.1/2 of KMW), we should give

Example2: If the domain of the computation is a skew of the domain of COR.1/2 of KMW, thr output should be

## No comments:

Post a Comment