Computational complexity

Java (and any other programming language) is modelled in terms of types and values. At the theoretical level, a value is a representation for some quantum of information, and a type is a set of values. When we say value X is an instance of type Y, we are simply saying that X is a member of the set of values that is the type Y.

So that’s what the term instance really means: it describes a relationship not a thing.

The type system of the Java programming language supports two kinds of types, primitive types and reference types. The reference types are further divided into the Classes and array types. A Java Object is (according to the JLS) an instance of a reference type; i.e. either an array or an instance of a Class.

That’s the type theoretic view.

In practice, most Java developers treat the words “instance” and “object” as synonyms. (And that includes me then I’m trying to explain something quickly.) And most developers use “value” rather than “instance” to refer to an instance of a primitive type.

Topics to be discussed:

  1. Complexity of problems
  2. Some problems are easy, some are hard
  3. The millennium prize problem – P vs NP
  4. Implications of P = NP
  5. Quantum computers – D Wave
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s