Conferences related to NP-complete problem

Back to Top

2020 IEEE International Symposium on Information Theory (ISIT)

Information theory, coding theory, communication theory, signal processing, and foundations of machine learning


ICC 2020 - 2020 IEEE International Conference on Communications

All topics relating to existing and emerging communications networking technologies.


GLOBECOM 2020 - 2020 IEEE Global Communications Conference

IEEE Global Communications Conference (GLOBECOM) is one of the IEEE Communications Society’s two flagship conferences dedicated to driving innovation in nearly every aspect of communications. Each year, more than 2,900 scientific researchers and their management submit proposals for program sessions to be held at the annual conference. After extensive peer review, the best of the proposals are selected for the conference program, which includes technical papers, tutorials, workshops and industry sessions designed specifically to advance technologies, systems and infrastructure that are continuing to reshape the world and provide all users with access to an unprecedented spectrum of high-speed, seamless and cost-effective global telecommunications services.


2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC)

The 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2020) will be held in Metro Toronto Convention Centre (MTCC), Toronto, Ontario, Canada. SMC 2020 is the flagship conference of the IEEE Systems, Man, and Cybernetics Society. It provides an international forum for researchers and practitioners to report most recent innovations and developments, summarize state-of-the-art, and exchange ideas and advances in all aspects of systems science and engineering, human machine systems, and cybernetics. Advances in these fields have increasing importance in the creation of intelligent environments involving technologies interacting with humans to provide an enriching experience and thereby improve quality of life. Papers related to the conference theme are solicited, including theories, methodologies, and emerging applications. Contributions to theory and practice, including but not limited to the following technical areas, are invited.


2020 59th IEEE Conference on Decision and Control (CDC)

The CDC is the premier conference dedicated to the advancement of the theory and practice of systems and control. The CDC annually brings together an international community of researchers and practitioners in the field of automatic control to discuss new research results, perspectives on future developments, and innovative applications relevant to decision making, automatic control, and related areas.



Periodicals related to NP-complete problem

Back to Top

Communications Letters, IEEE

Covers topics in the scope of IEEE Transactions on Communications but in the form of very brief publication (maximum of 6column lengths, including all diagrams and tables.)


Communications, IEEE Transactions on

Telephone, telegraphy, facsimile, and point-to-point television, by electromagnetic propagation, including radio; wire; aerial, underground, coaxial, and submarine cables; waveguides, communication satellites, and lasers; in marine, aeronautical, space and fixed station services; repeaters, radio relaying, signal storage, and regeneration; telecommunication error detection and correction; multiplexing and carrier techniques; communication switching systems; data communications; and communication theory. In addition to the above, ...


Computational Biology and Bioinformatics, IEEE/ACM Transactions on

Specific topics of interest include, but are not limited to, sequence analysis, comparison and alignment methods; motif, gene and signal recognition; molecular evolution; phylogenetics and phylogenomics; determination or prediction of the structure of RNA and Protein in two and three dimensions; DNA twisting and folding; gene expression and gene regulatory networks; deduction of metabolic pathways; micro-array design and analysis; proteomics; ...


Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Methods, algorithms, and human-machine interfaces for physical and logical design, including: planning, synthesis, partitioning, modeling, simulation, layout, verification, testing, and documentation of integrated-circuit and systems designs of all complexities. Practical applications of aids resulting in producible analog, digital, optical, or microwave integrated circuits are emphasized.


Computers, IEEE Transactions on

Design and analysis of algorithms, computer systems, and digital networks; methods for specifying, measuring, and modeling the performance of computers and computer systems; design of computer components, such as arithmetic units, data storage devices, and interface devices; design of reliable and testable digital devices and systems; computer networks and distributed computer systems; new computer organizations and architectures; applications of VLSI ...



Most published Xplore authors for NP-complete problem

Back to Top

Xplore Articles related to NP-complete problem

Back to Top

A Computational Model for Inference Chains in Expert Systems

2009 International Conference on Intelligent Engineering Systems, 2009

This paper deals with the calculations performed in the reasoning process of rule-based expert systems, where inference chains are applied. It presents a logic model for representing the rules and the rule base of a given system. Also, the fact base of the same expert system is involved in the logic model. The proposed equivalent representation manifests itself in a ...


Succinctness, verifiability and determinism in representations of polynomial-time languages

20th Annual Symposium on Foundations of Computer Science (sfcs 1979), 1979

Several representations of P, the class of deterministic polynomial time acceptable languages, are compared with respect to succinctness. It is shown that requirements such as polynomial running time, verifiability of running time, and verifiability of accepting a set in P can be causes for differences in succinctness that are not recursively bounded. Relating succinctness to nondeterminism, it is shown that ...


PRUNER: algorithms for finding monad patterns in DNA sequences

Proceedings. 2004 IEEE Computational Systems Bioinformatics Conference, 2004. CSB 2004., 2004

We present new algorithms for discovering monad patterns in DNA sequences. Monad patterns are of the form (l,d)-k, where l is the length of the pattern, d is the maximum number of mismatches allowed, and k is the minimum number of times the pattern is repeated in the given sample. The time-complexity of some of the best known algorithms to ...


An evolutionary heuristic for knowledge base partitioning problem

Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97), 1997

In this paper, I have tried to give an evolutionary heuristic to the knowledge base partitioning problem, which is a well-known NP-complete problem. There are different heuristics already existing to this end. After proposing my scheme, I make a comparative study in relation to the relative performance of my scheme vis-a/spl grave/-vis an existing genetic algorithm on the same benchmark. ...


An Effective Algorithm for the Design of the Optimal FIR Filters with Discrete Coefficients

2006 IEEE International Conference on Industrial Technology, 2006

This paper is dedicated to the important problem of digital FIR filters with linear phase and discrete coefficients design. The proposed algorithm provide an optimal solution. In order to reduce algorithm complexity, an localization using a sequential reduction of admissible values space is conducted. The adopted approach is illustrated by a simple example. The obtained results have been very promising. ...



Educational Resources on NP-complete problem

Back to Top

IEEE-USA E-Books

  • A Computational Model for Inference Chains in Expert Systems

    This paper deals with the calculations performed in the reasoning process of rule-based expert systems, where inference chains are applied. It presents a logic model for representing the rules and the rule base of a given system. Also, the fact base of the same expert system is involved in the logic model. The proposed equivalent representation manifests itself in a logic network. After that, a four-valued logic algebra is introduced. This algebra is used for the calculations where forward chaining is carried out. Next, the notion of line-value justification is described. This operation is applied in the backward chaining process, also on the base of the previously introduced four- valued logic. The paper describes two exact algorithms which serve for the forward and backward chaining processes. These algorithms make it possible to be implemented by a computer program, resulting in an efficient inference engine of an expert system. The achieved result enhances the reliability and usability of the intelligent software systems which is extremely important in embedded environments.

  • Succinctness, verifiability and determinism in representations of polynomial-time languages

    Several representations of P, the class of deterministic polynomial time acceptable languages, are compared with respect to succinctness. It is shown that requirements such as polynomial running time, verifiability of running time, and verifiability of accepting a set in P can be causes for differences in succinctness that are not recursively bounded. Relating succinctness to nondeterminism, it is shown that P ≠ NP if and only if the relative succinctness of representing languages in P by deterministic and nondeterministic clocked polynomial time machines is not recursively bounded. questions are posed, concerning the implications of P = NP, with respect to translatability and succinctness between other pairs of deterministic and nondeterministic representations for P.

  • PRUNER: algorithms for finding monad patterns in DNA sequences

    We present new algorithms for discovering monad patterns in DNA sequences. Monad patterns are of the form (l,d)-k, where l is the length of the pattern, d is the maximum number of mismatches allowed, and k is the minimum number of times the pattern is repeated in the given sample. The time-complexity of some of the best known algorithms to date is O(nt/sup 2/l/sup d/|/spl Sigma/|/sup d/2/), where t is the number of input sequences, and n is the length of each input sequence. The first algorithm that we present takes O(n/sup 2/t/sup 2/l/sup d/2/|/spl Sigma/|/sup d/2/) and space O(ntl/sup d/2/|/spl Sigma/|/sup d/2/), and the second algorithm takes O(n/sup 3/t/sup 3/l/sup d/2/|/spl Sigma/|/sup d/2/ time using O(l/sup d/2/|/spl Sigma/|/sup d/2/) space. In practice, our algorithms have much better performance provided the d/l ratio is small.

  • An evolutionary heuristic for knowledge base partitioning problem

    In this paper, I have tried to give an evolutionary heuristic to the knowledge base partitioning problem, which is a well-known NP-complete problem. There are different heuristics already existing to this end. After proposing my scheme, I make a comparative study in relation to the relative performance of my scheme vis-a/spl grave/-vis an existing genetic algorithm on the same benchmark. I show how my algorithm has outperformed the existing one.

  • An Effective Algorithm for the Design of the Optimal FIR Filters with Discrete Coefficients

    This paper is dedicated to the important problem of digital FIR filters with linear phase and discrete coefficients design. The proposed algorithm provide an optimal solution. In order to reduce algorithm complexity, an localization using a sequential reduction of admissible values space is conducted. The adopted approach is illustrated by a simple example. The obtained results have been very promising. A comparative study with an example taken from the literature illustrates the proposed algorithm efficiency.

  • A Hardware Accelerator for SAT Solving

    The Boolean satisfiability problem (SAT) is a central problem in artificial intelligence, mathematical logic and computing theory with wide range of practical applications. Being an NP-complete problem, the used SAT's solving algorithm execution time influences the performance of SAT-based applications. FPGAs represent a promising technology for accelerating SAT solvers. In this paper, we present an FPGA-based SAT solver based on depth-first search. Our architecture exploits the fine granularity and massive parallelism of FPGAs to evaluate the SAT formula and perform conflict diagnosis. Conflict diagnosis helps pruning the search space by allowing nonchronological conflict directed backtracking. We compare our SAT solver with three other SAT solvers. The gain in performance is validated through DIMACS benchmarks suite

  • Improved Simulated Annealing Algorithm Solving for 0/1 Knapsack Problem

    0/1 knapsack problem belongs to combination optimization problem. Its optimal solution exists in the problem space including substantially large useless solutions besides optimal solutions. Differing with other SA (simulated annealing) algorithms that getting the approximate optimization solution from the whole problem space often need much computation time, this improved SA algorithm proposed in this paper avoided this disadvantage by extracting two kinds of solution spaces, i.e. all optimal solutions space and the most possible part optimal solutions space, from the whole space. Then to improve approximate solution quality some variables were introduced to record the maximum solution, which produced during annealing process but was possibly deserted because of Metropolis rule in SA. We applied this SA algorithm, general SA and greedy-based SA algorithm to knapsack problem. And experimental results showed that this algorithm only searching the two optimal spaces obtained better approximate results and largely decreased the time overhead compared with the other two algorithms searching whole space

  • Application of continuous Hopfield network to solve the TSP

    Traveling salesman problem (TSP) is a classic of difficult optimization problem. It is simple to describe, mathematically well characterized. But the actual best solution to TSP is computationally very hard, called a NP-complete problem. In this paper, continuous Hopfield network (CHN) is applied to solve TSP. The energy function to be minimized is determined both by constraints for a valid solution and by total length of touring path. Setting of parameters in energy function is crucial to the convergence and performance of the network. The role of each parameter is analyzed and criteria for choosing these parameters are described. Iterative computation algorithm of CHN is given. Computer simulation is conducted for 6-, City TSP. Some simulation results, such as convergence curve, iteration count, computation time, are used to evaluate this method.

  • Parallel self-reducibility

    The authors examine the relationship between the complexity of solving a decision problem with that of solving a search problem. In particular, if they are given a solution for a decision problem in the form of an oracle, they consider the difficulty of finding evidence supporting the decision. For example, suppose they have an oracle which, when given a graph, indicates whether that graph has a Hamilton cycle (HC). The authors goal is to find a Hamilton cycle in a graph, thus proving it has one. After defining their problems using a relational model they show that if any NP-complete problem is self-reducible in parallel, then all NP-complete problems are. They also show that all P-complete problems have parallel self-reductions. Under the (unlikely) assumption that NP=co-NP, it is shown that NP-complete problems can be self-reduced. However, probabilism can be shown to help: any NP-complete problem has a randomized parallel self-reduction. Finally, natural evidence for an NP problem is discussed.<<ETX>>

  • USAT: An Integrated Platform for Satisfiability Solving and Model Checking

    A platform named USAT that integrates several gate-level and RTL satisfiability solvers is described. USAT has a unified circuit model that can represent both gate-level and RTL circuits. USAT integrates other solvers by translating between various circuit formats via the unified circuit model. USAT also includes a circuit generator that can generate RTL circuits with specific features specified by users. USAT also has a native ATPG-based solver that can solve satisfiability problem at both gate-level and RTL. The effectiveness of USAT is demonstrated by applications in bounded model checking.



Standards related to NP-complete problem

Back to Top

No standards are currently tagged "NP-complete problem"