1,048 resources related to NP-complete problem
- Topics related to NP-complete problem
- IEEE Organizations related to NP-complete problem
- Conferences related to NP-complete problem
- Periodicals related to NP-complete problem
- Most published Xplore authors for NP-complete problem
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.
The International Conference on Image Processing (ICIP), sponsored by the IEEE SignalProcessing Society, is the premier forum for the presentation of technological advances andresearch results in the fields of theoretical, experimental, and applied image and videoprocessing. ICIP 2020, the 27th in the series that has been held annually since 1994, bringstogether leading engineers and scientists in image and video processing from around the world.
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 IEEE International Symposium on Information Theory (ISIT)
Information theory, coding theory, communication theory, signal processing, and foundations of machine learning
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.
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.)
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, ...
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; ...
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.
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 ...
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 ...
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 ...
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 ...
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. ...
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. ...
A perspective shift from Fuzzy logic to Neutrosophic Logic - Swati Aggarwal
Maker Faire 2008: Smart LEDs
The SLAM Problem - a Fifteen Year Journey...
Maker Faire 2008: Pong and Asteroids Watch
IMS 2011 Microapps - IQ Mixer Measurements: Techniques for Complete Characterization of IQ Mixers Using a Multi-Port Vector Network Analyzer
Hyper-heuristics: Towards Automated Heuristic Design 2
Hyper-heuristics: Towards Automated Heuristic Design 1
Nebbiolo Technologies Pitch: Fog Tank - Fog World Congress
Challenging the stigma surrounding the role of women in technology, a journey from combinatorial optimization to IBM
IEEE Authoring Part 9: Next Steps
Christos H. Papadimitriou accepts the IEEE John von Neumann Medal - Honors Ceremony 2016
Student Paper and Poster Winners - Carmen Menoni - Closing Ceremony, IPC 2018
A Recurrent Crossbar of Memristive Nanodevices Implements Online Novelty Detection - Christopher Bennett: 2016 International Conference on Rebooting Computing
Real-Time, Triggering, & Signal Capture for Agile and Elusive Signals (2)
Collaborative Filtering II
Genetic Programming Hyper-heuristics for Combinatorial Optimisation: Yi Mei CIS Webinar
Silicon Labs' Thunderboard Sense (SLTB001A): Mouser Engineering Bench Talk
2013 IEEE Presidents' Change The World Competition Winners
Low-energy High-performance Computing based on Superconducting Technology
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.
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.
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.
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.
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.
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
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
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.
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>>
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.
No standards are currently tagged "NP-complete problem"