Cook–Levin theorem by Mr.Mukesh Bhukar (Lecturer, CS/IT)

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to a problem of determining whether a Boolean formula is satisfiable.

An important consequence of the theorem is this: if there were a deterministic polynomial time algorithm for solving Boolean satisfiability, then there would exist a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem as these are also in NP.

The question of whether such an algorithm exists is called the P=NP problem and it is widely considered the most important unsolved problem in theoretical computer science.

Contributions

The concept of NP-completeness was developed in the late 1960s and early 70s in parallel by researchers in the US and the USSR. In the US in 1971, Stephen Cook published his paper "The complexity of theorem proving procedures" in conference proceedings of the newly-founded ACM Symposium on Theory of Computing. Richard Karp's subsequent paper, "Reducibility among combinatorial problems", generated renewed interest in Cook's paper by providing a list of 21 NP-complete problems. Cook and Karp received a Turing Award for this work.

The theoretical interest in NP-completeness was also enhanced by the work of Theodore P. Baker, John Gill, and Robert Solovay who showed that solving NP-problems in Oracle machine models requires exponential time.

In the USSR, a result equivalent to Baker, Gill, and Solovay's was published in 1969 by M. Dekhtiar. Later Levin's paper, "Universal search problems", was published in 1973, although it was mentioned in talks and submitted for publication a few years earlier.

Levin's approach was slightly different from Cook's and Karp's in that he considered search problems, which require finding solutions rather than simply determining existence. He provided 6 such NP-complete search problems, or universal problems, and additionally found that each has an algorithm which solves it in optimal time.

Definitions

A decision problem is in NP iff it can be solved by a non-deterministic algorithm in polynomial time.

An instance of the Boolean satisfiability problem is a Boolean expression that combines Boolean variables using Boolean operators.

An expression is satisfiable iff there is some assignment of truth values to the variables that makes the entire expression true.

Proof

This proof is based on the one given by Garey and Johnson.

There are two parts to proving that the Boolean satisfiability problem (SAT) is NP-complete. One is to show that SAT is an NP problem. The other is to show that every NP problem can be reduced to an instance of a SAT problem by a polynomial-time many-one reduction.

SAT is in NP because any assignment of Boolean values to Boolean variables that is claimed to satisfy the given expression can be verified in polynomial time by a deterministic Turing machine. This means that SAT is in NP by an equivalence theorem found in many textbooks, for example Sipser's Introduction to the Theory of Computation, section 7.3.

Now suppose that a given problem in NP can be solved by the nondeterministic Turing machine M = (Q,Σ,s,F,δ), where Q is the set of states, Σ is the alphabet of tape symbols, is the initial state, is the set of accepting states, and is the set of transitions. Suppose further that M accepts or rejects an instance of the problem in time p(n) where n is the size of the instance and p is a polynomial function.

For each input I we specify a Boolean expression which is satisfiable if and only if the machine M accepts I.

The Boolean expression uses the variables set out in the following table. Here, , , , and .

Variables	Intended interpretation	How many?
Tijk	True if tape cell i contains symbol j at step k of the computation.	O(p(n)²)
Hik	True if the M's read/write head is at tape cell i at step k of the computation.	O(p(n)²)
Qqk	True if M is in state q at step k of the computation.	O(p(n))

Define the Boolean expression B to be the conjunction of the clauses in the following table, for all and :

Clauses	Conditions	Interpretation	How many?
Tij0	Tape cell i of the input I contains symbol j.	Initial contents of the tape.	O(p(n))
Qs0		Initial state of M	O(1)
H00		Initial position of read/write head.	O(1)
Tijk → ¬ Tij′k	j ≠ j′	One symbol per tape cell.	O(p(n)²)
Tijk = Tij(k+1) ∨ Hik		Tape remains unchanged unless written.	O(p(n)²)
Qqk → ¬ Qq′k	q ≠ q′	Only one state at a time.	O(p(n))
Hik → ¬ Hi′k	i ≠ i′	Only one head position at a time.	O(p(n)²)
(Hik ∧ Qqk ∧ Tiσk) → (H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1))	(q, σ, q′, σ′, d) ∈ δ	Possible transitions at computation step k when head is at position i.	O(p(n)²)
The disjunction of the clauses Qf(p(n))	f ∈ F.	Must finish in an accepting state.	O(1)

If there is an accepting computation for M on input I, then B is satisfiable by assigning T_ijk, H_ik and Q_ik their intended interpretations. On the other hand, if B is satisfiable, then there is an accepting computation for M on input I that follows the steps indicated by the assignments to the variables.

There are O(p(n)²) Boolean variables, each encodeable in space O(logp(n)). The number of clauses is O(p(n)²) so the size of B is O(log(p(n))p(n)²). Thus the transformation is certainly a polynomial-time many-one reduction, as required.

Stepper motor By Mr.Rajesh Sharma (Lecturer, ECE)

A stepper motor (or step motor) is a brush less, synchronous electric motor that can divide a full rotation into a large number of steps. The motor's position can be controlled precisely, without any feedback mechanism (see open loop control). Stepper motors are similar to switched reluctance motors (which are very large stepping motors with a reduced pole count, and generally are closed-loop commutated.)

Fundamentals of Operation

Stepper motors operate differently from normal DC motors, which rotate when voltage is applied to their terminals. Stepper motors, on the other hand, effectively have multiple "toothed" electromagnets arranged around a central gear-shaped piece of iron. The electromagnets are energized by an external control circuit, such as a microcontroller. To make the motor shaft turn, first one electromagnet is given power, which makes the gear's teeth magnetically attracted to the electromagnet's teeth. When the gear's teeth are thus aligned to the first electromagnet, they are slightly offset from the next electromagnet. So when the next electromagnet is turned on and the first is turned off, the gear rotates slightly to align with the next one, and from there the process is repeated. Each of those slight rotations is called a "step," with an integral number of steps making a full rotation. In that way, the motor can be turned by a precise angle.

Stepper motor characteristics
Stepper motors are constant power devices. As motor speed increases, torque decreases. The torque curve may be extended by using current limiting drivers and increasing the driving voltage.
Steppers exhibit more vibration than other motor types, as the discrete step tends to snap the rotor from one position to another. This vibration can become very bad at some speeds and can cause the motor to lose torque. The effect can be mitigated by accelerating quickly through the problem speed range, physically damping the system, or using a micro-stepping driver. Motors with a greater number of phases also exhibit smoother operation than those with fewer phases.


Stepper motor ratings and specifications
Stepper motors nameplates typically give only the winding current and occasionally the voltage and winding resistance. The rated voltage will produce the rated winding current at DC: but this is mostly a meaningless rating, as all modern drivers are current limiting and the drive voltages greatly exceed the motor rated voltage.
A stepper's low speed torque will vary directly with current. How quickly the torque falls off at faster speeds depends on the winding inductance and the drive circuitry it is attached to, especially the driving voltage.
Steppers should be sized according to published torque curve, which is specified by the manufacturer at particular drive voltages and/or using their own drive circuitry. It is not guaranteed that you will achieve the same performance given different drive circuitry, so the pair should be chosen with great care.

Applications
Computer-controlled stepper motors are one of the most versatile forms of positioning systems. They are typically digitally controlled as part of an open loop system, and are simpler and more rugged than closed loop servo systems.
Industrial applications are in high speed pick and place equipment and multi-axis machine CNC machines often directly driving lead screws or ballscrews. In the field of lasers and optics they are frequently used in precision positioning equipment such as linear actuators, linear stages, rotation stages, goniometers, and mirror mounts. Other uses are in packaging machinery, and positioning of valve pilot stages for fluid control systems.
Commercially, stepper motors are used in floppy disk drives, flatbed scanners, computer printers, plotters and many more devices.

Cloud computing v/s Grid Computing By Mr.Arjun Ram (Lecturer, CS/IT)

Introduction

You may have wondered about cloud computing as compared to grid computing. In this article, I talk about cloud computing service types and the similarities and differences between cloud and grid computing. I look at why cloud computing may be advantageous over grid computing, what issues to consider in both, and some security concerns. I use Amazon Web Services as an example.

To get cloud computing to work, you need three things: thin clients (or clients with a thick-thin switch), grid computing, and utility computing. Grid computing links disparate computers to form one large infrastructure, harnessing unused resources. Utility computing is paying for what you use on shared servers like you pay for a public utility (such as electricity, gas, and so on).

With grid computing, you can provision computing resources as a utility that can be turned on or off. Cloud computing goes one step further with on-demand resource provisioning. This eliminates over-provisioning when used with utility pricing. It also removes the need to over-provision in order to meet the demands of millions of users.

Cloud computing

With cloud computing, companies can scale up to massive capacities in an instant without having to invest in new infrastructure, train new personnel, or license new software. Cloud computing is of particular benefit to small and medium-sized businesses who wish to completely outsource their data-center infrastructure, or large companies who wish to get peak load capacity without incurring the higher cost of building larger data centers internally. In both instances, service consumers use what they need on the Internet and pay only for what they use.

The service consumer no longer has to be at a PC, use an application from the PC, or purchase a specific version that's configured for smartphones, PDAs, and other devices. The consumer does not own the infrastructure, software, or platform in the cloud. He has lower upfront costs, capital expenses, and operating expenses. He does not care about how servers and networks are maintained in the cloud. The consumer can access multiple servers anywhere on the globe without knowing which ones and where they are located.

Grid computing

Cloud computing evolves from grid computing and provides on-demand resource provisioning. Grid computing may or may not be in the cloud depending on what type of users are using it. If the users are systems administrators and integrators, they care how things are maintained in the cloud. They upgrade, install, and virtualize servers and applications. If the users are consumers, they do not care how things are run in the system.

Grid computing requires the use of software that can divide and farm out pieces of a program as one large system image to several thousand computers. One concern about grid is that if one piece of the software on a node fails, other pieces of the software on other nodes may fail. This is alleviated if that component has a failover component on another node, but problems can still arise if components rely on other pieces of software to accomplish one or more grid computing tasks. Large system images and associated hardware to operate and maintain them can contribute to large capital and operating expenses.

Similarities and differences

Cloud computing and grid computing are scalable. Scalability is accomplished through load balancing of application instances running separately on a variety of operating systems and connected through Web services. CPU and network bandwidth is allocated and de-allocated on demand. The system's storage capacity goes up and down depending on the number of users, instances, and the amount of data transferred at a given time.

Both computing types involve multitenancy and multitask, meaning that many customers can perform different tasks, accessing a single or multiple application instances. Sharing resources among a large pool of users assists in reducing infrastructure costs and peak load capacity. Cloud and grid computing provide service-level agreements (SLAs) for guaranteed uptime availability of, say, 99 percent. If the service slides below the level of the guaranteed uptime service, the consumer will get service credit for receiving data late.

The Amazon S3 provides a Web services interface for the storage and retrieval of data in the cloud. Setting a maximum limits the number of objects you can store in S3. You can store an object as small as 1 byte and as large as 5 GB or even several terabytes. S3 uses the concept of buckets as containers for each storage location of your objects. The data is stored securely using the same data storage infrastructure that Amazon uses for its e-commerce Web sites.

While the storage computing in the grid is well suited for data-intensive storage, it is not economically suited for storing objects as small as 1 byte. In a data grid, the amounts of distributed data must be large for maximum benefit.

A computational grid focuses on computationally intensive operations. Amazon Web Services in cloud computing offers two types of instances: standard and high-CPU.

Issues to consider

Four issues stand out with cloud and grid computing: threshold policy, interoperability issues, hidden costs, and unexpected behavior.

Threshold policy

Let's suppose I had a program that did credit card validation in the cloud, and we hit the crunch for the December buying season. Higher demand would be detected and more instances would be created to fill that demand. As we moved out of the buying crunch, the need would be diminished and the instances of that resource would be de-allocated and put to other use.

To test if the program works, develop, or improve and implement, a threshold policy in a pilot study before moving the program to the production environment. Check how the policy detects sudden increases in the demand and results in the creation of additional instances to fill in the demand. Also check to determine how unused resources are to be de-allocated and turned over to other work.

Interoperability issues

If a company outsource or creates applications with one cloud computing vendor, the company may find it is difficult to change to another computing vendor that has proprietary APIs and different formats for importing and exporting data. This creates problems of achieving interoperability of applications between these two cloud computing vendors. You may need to reformat data or change the logic in applications. Although industry cloud-computing standards do not exist for APIs or data import and export, IBM and Amazon Web Services have worked together to make interoperability happen.

Hidden costs

Cloud computing does not tell you what hidden costs are. For instance, companies could incur higher network charges from their service providers for storage and database applications containing terabytes of data in the cloud. This outweighs costs they could save on new infrastructure, training new personnel, or licensing new software. In another instance of incurring network costs, companies who are far from the location of cloud providers could experience latency, particularly when there is heavy traffic.

Unexpected behavior

Let's suppose your credit card validation application works well at your company's internal data center. It is important to test the application in the cloud with a pilot study to check for unexpected behavior. Examples of tests include how the application validates credit cards, and how, in the scenario of the December buying crunch, it allocates resources and releases unused resources, turning them over to other work. If the tests show unexpected results of credit card validation or releasing unused resources, you will need to fix the problem before running the application in the cloud.

Conclusion

This article helps you plan ahead for working with cloud by knowing how cloud computing compares to grid computing, how you can resolve issues in cloud and grid computing, and what security issues exist with data recovery and managing private keys in a pay-on-demand environment. Potential consumers' demands for increased capacities over the Internet present a challenge for the developers and other members of a project team. Being aware of and resolving the issues of Web application design and potential security issues can make your team's experiences trouble-free. To help, look at IBM Rational Web Developer Web Sphere Software to build Web applications and IBM Rational Clear Quest for defect and application tracking.

Wi-Fi Introduction By Tushar (2nd Year, CS)

Wireless Technology is an alternative to Wired Technology, which is commonly used, for connecting devices in wireless mode. Wi-Fi (Wireless Fidelity) is a generic term that refers to the IEEE 802.11 communications standard for Wireless Local Area Networks (WLANs). Wi-Fi Network connect computers to each other, to the internet and to the wired network.

The name of a popular wireless networking technology that uses radio waves to provide wireless high-speed Internet and network connections. The Wi-Fi Alliance, the organization that owns the Wi-Fi term specifically defines Wi-Fi as any "wireless local area network (WLAN) products that are based on the Institute of Electrical and Electronics Engineers' (IEEE) 802.11 standards."

Wi-Fi works with no physical wired connection between sender and receiver by using radio frequency (RF) technology, a frequency within the electromagnetic spectrum associated with radio wave propagation. When an RF current is supplied to an antenna, an electromagnetic field is created that then is able to propagate through space. The cornerstone of any wireless network is an access point (AP). The primary job of an access point is to broadcast a wireless signal that computers can detect and "tune" into.

Wi-Fi is supported by many applications and devices including video game consoles, home networks, PDAs, mobile phones, major operating systems, and other types of consumer electronics. Any products that are tested and approved as "Wi-Fi Certified" (a registered trademark) by the Wi-Fi Alliance are certified as interoperable with each other, even if they are from different manufacturers. For example, a user with a Wi-Fi Certified product can use any brand of access point with any other brand of client hardware that also is also "Wi-Fi Certified". Wi-Fi cards - They accept the wireless signal and relay information.They can be internal and external.(e.g PCMCIA Card for Laptop and PCI Card for Desktop PC). Safeguards - Firewalls and anti-virus software protect networks from uninvited users and keep information secure.

Wireless Communications, various telecommunications systems that use radio waves to carry signals and messages across distances. Wireless communications systems include cellular telephones, pagers, radio telegraphs, satellite telephones, laptop computers, personal digital assistants (PDAs), shortwave radios, and two-way radios. They are used primarily to transmit private communications. Commercial radio and television are also wireless telecommunications systems, but radio and television are mainly public broadcast services rather than private communications systems (see Radio and Television Broadcasting).

Wireless communications allow people greater flexibility while communicating, because they do not need to remain at a fixed location, such as a home or office, but instead can communicate with other people while traveling in a car or walking along a street. Wireless technologies make communications services more readily available than traditional wire-based services (such as ordinary telephones), which require the installation of wires in fixed locations. Wireless communications devices are useful in places where communications services are only temporarily needed, such as at outdoor festivals or large sporting events. These technologies are also useful for communicating in remote locations, such as mountains, jungles, or deserts, where wire-based telephone service might not exist.

All wireless communications devices use radio waves to transmit and receive signals. These devices operate on different radio frequencies so that signals from one device will not overlap and interfere with nearby transmissions from other devices. The number of companies offering wireless communications services have grown steadily in recent years. Currently, telecommunications companies throughout the world are activating more wireless service subscriptions than they are conventional wire-based service subscriptions. Wireless communication is becoming increasingly popular because of the convenience and mobility it affords; the expanded availability of radio frequencies for transmitting, which makes it possible to handle a larger volume of calls; and improvements in technology, which have added other services such as Internet access and improved the clarity of voice transmissions.